정렬 알고리즘

  1. 정렬
    1. 버블 정렬 (Bubble Sort)
    2. 삽입 정렬 (Insert Sort)
    3. 선택 정렬 (Selection Sort)
    4. 병합 정렬 (Merge Sort)
    5. 힙 정렬 (Heap Sort)
    6. 퀵 정렬 (Quick Sort)
    7. 트리 정렬
    8. 기수 절렬(Radix Sort)
    9. 계수 정렬
    10. 셀 정렬

정렬

버블 정렬 (Bubble Sort)

인접한 데이터를 비교하며 자리를 바꾸는 방식

복잡도: O(N^2) => (n-1)+(n-2)+…+2+1

삽입 정렬 (Insert Sort)

앞의 데이터를 정렬하면서 삽입 위치를 찾아 정렬하는 방식

복잡도: O(N^2) => (n-1)+(n-2)+…+2+1

선택 정렬 (Selection Sort)

최소 또는 최대값을 찾아서 가장 앞 또는 뒤부터 정렬하는 방식

image

복잡도: O(N^2) => (n-1)+(n-2)+…+2+1

병합 정렬 (Merge Sort)

배열을 분할하여 길이가 1이 되도록 만들고 인접한 부분끼리 정렬하면서 합병하는 방식

알고리즘 복잡도: O(nlogn)

힙 정렬 (Heap Sort)

힙 자료구조 형태의 정렬 방식

알고리즘 복잡도: O(nlogn)

퀵 정렬 (Quick Sort)

임의의 기준값을 정하고 기준의 좌우로 분할하여 정렬하는 방식
복잡도: O(n^2)
[WARGING]
“Partition” 함수 내용과 같이 pivot을 왼쪽에서 한다면 오른쪽부터 탐색을 해야하고
반대로 pivot을 오른쪽에 둔다면 왼쪽부터 탐색해야한다.

def quick_sort(array,start,end):
    if start >= end:
        return
    pivot = start
    left, right = start + 1, end
    while(left <= right):
        while(left <= end and array[left] <= array[pivot]):
            left +=1
        while(right > start and array[right] >= array[pivot]):
            right -=1
        if(left >right):
            array[right],array[pivot] = array[pivot],array[right]
        else:
            array[left],array[right] = array[right] ,array[left]
    
    quick_sort(array, start, right-1)
    quick_sort(array, right+1, end)

arr = [4,2,3,1,9,7]

quick_sort(arr,0,len(arr)-1)
print(arr)

트리 정렬

이진 탐색 트리(BST)를 만들어 정렬하는 방식

복잡도: O(nlogn)

기수 절렬(Radix Sort)

낮은 자리 수부터 정렬하는 방식

  • 각 원소간의 비교 연산을 하지 않아 빠른 대신 기수 테이블을 위한 메모리 필요.

복잡도: O(dn) //d: 최대 자릿수

1차 과정 - 1의 자리

10325227481799562376
[0][1][2][3][4][5][6][7][8][9]

2차 과정 - 10의 자리

10325223765627174899
[0][1][2][3][4][5][6][7][8][9]

계수 정렬

카운트를 세서 정렬하는 방식

  • 카운팅을 위한 메모리 필요

복잡도: O(n+k) //k: 정렬 대상 데이터 중 최대값

셀 정렬

삽입 정렬의 약점을 보완한 정렬 방식

** 삽입 정렬의 약점 **

  • 오름차순 정렬 기준이나 내림차순으로 구성된 데이터에 대해서는 앞의 데이터와 하나씩 비교하며 모두 교환 필요

  • 일정 간격을 두어 비교 //간격(GAP)은 (배열길이/2)로 설정

복잡도: O(n^2)

87654321
8   4   
 7   3  
  6   2 
   5   1