정렬 알고리즘 (삽입,선택,버블,셸,퀵,힙,병합 정렬)

✨ 정렬 알고리즘  

크래프톤 정글에서 퀵 정렬에 대해서 쪽지 시험이 나왔다. 

퀵 정렬을 공부하면서 다른 정렬 방법에 대해서도 궁금증이 생겼고, 

책과 블로그들을 참고하면서 정리 해보았다. 

 

---

🔖 Insertion sort (삽입 정렬) 

삽입 정렬은 손안의 카드를 정렬하는 방법과 유사하다.  새로운 카드를 기존 정렬된 카드 사이 올바른 위치에 삽입한다. 

key 값은 2번째 인덱스부터 시작되며, key 값이 자료의 길이만큼 이동되면 정렬이 완성된다. 

 

 

특징 : 

1. 안전한 정렬 방법이다. (바로 옆의 데이터와 비교 )

→ 안전하다는 것을 동일한 값을 가진 원소들의 상대적인 순서가 유지되는 것을 의미

2. 이미 정렬되어 있는 경우나 자료의 수가 적을 경우 구현이 간단

3. 비교적으로 많은 레코드들의 이동이 필요하다. 

4. 자료의 수가 많고 자료의 크기가 클 경우 적합하지 않다

 

 

 

🔖 Selection sort (선택 정렬) 

선택 정렬은 첫 번째 레코드를 두 번째 레코드부터 마지막 레코드까지 차례대로 비교하여 가장 작은 값을 찾아 첫 번째에 놓는다. 두 번째 레코드는 세번째 레코드부터 마지막 레코드까지 비교하여 그 중 가장 작은 값을 찾아  두 번째 위에 놓는다. 1회전 수행하고 나면 가장 작은 레코드는 가장 맨 앞으로 오게 된다.  

 

특징 : 

1. 자료 이동 횟수가 미리 결정된다.

2. 불안정 정렬 방식이다. 

3. 값이 같은 레코드가 있는 경우 상대적 위치가 변경된다. 

4. 제자리 정렬 알고리즘이다.  (입력 배열 이외에 다른 추가 메모리 요구하지 않음) 

 

[예시 코드]

def selection_sort(arr):
    for i in range(len(arr) - 1):
        min_idx = i
        for j in range(i + 1, len(arr)):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]

 

 

 

🔖 Bubble sort (버블 정렬) 

버블 정렬은 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘이다. 인접한 2개의 레코드를 비교하고 필요에따라 자리를 교환하는 정렬 방식이다. 

 

 

특징 : 

1. 최악의 경우와 평균의 경우 모두 O(n^2) 이다. 

2. 주어진 리스트 외에 추가적인 메모리를 사용하지 않으므로 O(1)이다. 

3. 동일한 값의 요소들이 순서를 유지하여 안정적인 알고리즘이다. 

 

버블 정렬은 구현이 간단하고 우리가 흔히 생각 할 수있는 정렬이라고 생각한다.

 

[예시 코드]

def bubbleSort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]: 
                arr[j], arr[j + 1] = arr[j + 1], arr[j]

 

 

🔖 Shell sort (셸 정렬) 

삽입정렬에서 요소들이 삽입될 때, 이웃한 위치로만 이동한다.

삽입되어야 할 위치가 멀리 떨어진 경우 많은 이동을 해야 제자리로 돌아 갈 수 있다.

셸정렬은 삽입 정렬을 보완한 알고리즘이다. 

연속적이지 않은 여러 개의 부분 리스트를 생성한다.

그리고 각 부분 리스트를 삽입 정렬을 이용하여 정렬한다.  

모든 부분 리스트가 정렬되면 다시 전체리스트를  더 적은 개수의 부분 리스트로 만든 후 알고리즘 반복한다. 

부분 리스트의 개수가 1일 될 때까지 반복한다. 

 

 

구현 개념이 좀 헷갈릴수도 있다. 

정렬해야 할 리스트의 각 k번째 요소를 추출해서 부분 리스트를 만든다.

k를 간격 gap이라고 한다. 

 

→ 간격 초기값 : 정렬할 값의 수 / 2  

→ 생성된 부분 리스트의 개수 : gap과 같음 

 

 

 

각 회전마다 간격 k를 절반으로 줄인다.  (간격은 왠만하면 홀수로 하는 것이 좋고, 짝수가 나올 경우 +1로 홀수로 만든다) 그리고 간격이 1이될때까지 반복한다.  

 

특징 : 

1. 연속적이지 않은 부분 리스트에서 자료의 교환이 일어나면 더 큰 거리를 이동한다.

따라서 교환되는 요소들이 삽입 정렬보다 최종 위치에 있을 가능성이 높다.

 

2. 부분 리스트는 어느정도 정렬이 된 상태이다. 부분 리스트의 개수가 1이 되게 되면 셸정렬은 기본적으로 삽입 정렬을 수

행하는 것이지만 삽입 정렬보다 더욱 빠르게 수행된다 .

 

[예시 코드]

def shell_sort(arr):
    n = len(arr)
    gap = 1
    while gap < n // 3:
        gap = gap * 3 + 1  # Sedgewick gap sequence

    while gap >= 1:
        for i in range(gap, n):
            temp = arr[i]
            j = i
            while j >= gap and arr[j - gap] > temp:
                arr[j] = arr[j - gap]
                j -= gap
            arr[j] = temp
        gap //= 3
    return arr

 

 

 

 

🔖  Heap sort (힙 정렬) 

힙은 완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 구조이다. 힙은 최댓값과 최소값을 쉽게 추출할 수 있는 자료구조이다.

힙 정렬은 최대 힙 트리나 최소 힙 트리를 구성해 정렬을 하는 방법이다. 

 

(내림차순 정렬 최대힙 구현)

1. 정렬해야 할 n개의 요소들로 최대 힙을 만든다. 

2. 그 다음 한 번에 하나씩 요소를 힙에서 꺼내서 배열의 뒤부터 저장한다. 

3. 정렬해야 할 n 개의 요소들을 1차원 배열에 기억한 후 최대 힙 삽입을 통해 차례대로 삽입한다. 

4. 최대 힙으로 구성된 배열에서 최댓값부터 삭제한다.

5. 자기보다 큰 값을 가지는 자식 요소와 자리를 바꾸며 아래쪽으로 내려가는 잡업을 반복한다.

 

 

이 과정 적용하기 전에 배열을 힙 상태로 만들어야 한다. 이후 정렬을 마치게 된다면, 정렬하지 않은 부분의 요소를 힙으로 만들어야한다. 

 

특징 : 

시간 복잡도가 좋은 편이다. 힙정렬은 가장 크거나 작은 값 일부만 필요할 때 유용하다. 

힙 트리의 전체 높이가 거의 log2n (완전 이진 트리)이므로 하나의 요소를 힙에 삽입하거나 삭제할 때 힙을 재정비하는 시간이 log2n만큼 소요된다. 

 

 

 

🔖 Quick sort (퀵 정렬) 

정렬에는 많은 방법들이 있다. 그중 퀵 정렬은 매우 빠르게 정렬을 수행하는 알고리즘이다. 

 

- 개념 : 

주어진 배열에서 하나의 요소(피벗)를 선택한다. 

배열 내부의 모든 값을 검사하면서 피벗값보다 작은 값들을 왼쪽, 큰 값들은 오른쪽에 배치한다. 

이렇게 남은 배열들을 다시 각각 새로운 피벗을 만들어 두개의 배열로 다시 쪼개준다. 

더 이상 쪼갤 수 없을 때까지 진행한다. 

 

피벗 중심으로 문제를 분할하고 작은 값과 큰 값을 나열하는 정복과정을 가지고 모든 결과를 결합한다. 

 

특징 : 

1. 기본적으로 분할정복의 성격을 가짐 

2. 평균 시간 복잡도 ( O(nlogn) 피벗이 균등하게 분할) 

3. 최악 시간 복잡도 ( O(n^2) ) 피벗이 항상 최소값이나 최대값으로 선택되는 경우

4. 추가적인 메모리를 거의 사용하지 않으며 평균적으로 매우 빠른 실행 

5. 최악의 경우 시간 복잡도가 O(n^2) 까지 증가할 수 있고,

안정 정렬이 아니므로 동일한 값을 가진 요소의 상대적 순서가 변경된다. 

6. 추가적인 메모리 사용이 거의 없으며, 제자리 정렬이 가능하다. 

 

퀵 정렬은 최악의 경우를 피하기위해 피벗 선택 방법이 중요하고,

일반적으로 무작위 선택이나 중앙값 등의 기법을 사용하여 최악의 시나리오 발생 확률은 줄인다.   

 

예시 코드 

def quickSort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quickSort(left) + middle + quickSort(right)

# 예시 배열
arr = [3, 6, 8, 10, 1, 2, 1]
sorted_arr = quickSort(arr)
print("정렬된 배열:", sorted_arr)

 

해당 파이썬 구현 코드는 생각보다 간단하다 . 

교과서에서 나온 코드를 보다 이걸 보니 이게 맞나? 라는 생각이 들었다.

 

하지만 left, middle, right 의 리스트 생성이 메모리 차지에 걱정은 없다. 

해당 리스트들은 OS의 stack에 들어가기 때문에 큰 상관을 안해도 된다. 

 

 

 

🔖 Merge sort (병합 정렬) 

폰 노이만이 제안한 방법이다. 이 정렬은 안정 정렬에 속하고, 분할 정복 알고리즘의 하나이다. 

리스트의 길이가 0 또는 1 이면 이미 정렬된 것으로 본다.

정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다. 

각 부분 리스트를 재귀적으로 합병 정렬한다. 

 

합병 정렬 과정에 추가적인 리스트가 필요하다.

각 부분 배열을 정렬할 때도 합병 정렬을 순환적으로 호출하여 적용한다. 

실제로 정렬이 이뤄지는 시점은 2개의 리스트 합병하는 단계이다. 

 

 

 

 

2개의 리스트의 값들을 처음부터 하나씩 비교하여 두개의 리스트 값 중에서 더 작은 값을 새로운 리스트로 옮긴다. 

둘 중에서 하나가 끝날 때까지 이 과정을 되풀이한다. 

만약 둘 중에서 하나의 리스트가 먼저 끝나게 되면 나머지 리스트의 값들을 전부 새로운 리스트로 복사한다.

 

특징 : 

레코드를 배열로 구성하면, 임시 배열이 필요하다. (제자리 정렬이 아님)

레코드들의 크기가 큰 경우 이동 횟수가 많아 매우 큰 시간적 낭비를 한다. 

입력 데이터가 무엇이든 간에 정렬되는 시간은 동일하다. 

만약 레코드를 연결 리스트로 구성하면 링크 인덱스만 변경되어 데이터의 이동은 무시할 수 있을정도로 작아진다. 

 

예제코드

def merge_sort(arr):
    if len(arr) < 2:
        return arr

    mid = len(arr) // 2
    low_arr = merge_sort(arr[:mid])
    high_arr = merge_sort(arr[mid:])

    merged_arr = []
    l = h = 0
    while l < len(low_arr) and h < len(high_arr):
        if low_arr[l] < high_arr[h]:
            merged_arr.append(low_arr[l])
            l += 1
        else:
            merged_arr.append(high_arr[h])
            h += 1
    merged_arr += low_arr[l:]
    merged_arr += high_arr[h:]
    return merged_arr

 

 

 

(참고)

안전 정렬  : 삽입 버블  병합 

불안정 정렬 : 선택  힙 퀵