[알고리즘] 정렬

 

이름	최선	평균	최악	메모리	안정
버블 정렬	O(n)	O(n^2)	O(n^2)	1	Y
선택 정렬	O(n^2)	O(n^2)	O(n^2)	1	N
삽입 정렬	O(n)	O(n^2)	O(n^2)	1	Y
힙 정렬	O(n) 모든 키가 구별 되는 경우 O(nlogn)	O(nlogn)	O(nlogn)	1	N
병합 정렬	O(nlogn)	O(nlogn)	O(nlogn)	n	Y
퀵 정렬	O(nlogn)	O(nlogn)	O(n^2)	logn

 

버블 정렬

• 수열의 오른쪽 끝에 저울을 두고 저울의 좌우에 있는 숫자를 비교합니다.
• 만약 왼쪽의 숫자보다 오른쪽의 숫자가 더 작다면, 교환합니다.
• 이후 저울을 한 칸 왼쪽으로 옮깁니다. 동일한 방법으로 숫자를 비교하고 교환합니다.
• 이 과정을 저울이 가장 왼쪽에 올 때까지 반복합니다.
•  이렇게 저울을 한 번 왼쪽에서 오른쪽으로 옮기면 가장 왼쪽에는 작은 값이 위치해있게 됩니다.
• 그 다음 다시 저울을 오른쪽으로 옮긴 후 위와 같은 과정을 배열 속 원소의 개수만큼 반복합니다.

 

 

선택 정렬

• 수열 전체를 대상으로 탐색해서 최솟값을 찾습니다.
• 최솟값을 배열의 첫 번째에 위치한 숫자와 교환하고 정렬을 완료합니다.
• 첫 번째 원소를 제외한 나머지 원소를 대상으로 탐색하여 최솟값을 찾습니다.
• 최솟값을 배열의 두 번째에 위치한 숫자와 교환하고 정렬을 완료합니다.
• ...
• 마지막 원소까지 위 과정을 반복합니다.

https://hudi.kr/%EC%A0%95%EB%A0%AC-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-1-%EC%84%A0%ED%83%9D-%EC%A0%95%EB%A0%AC-selection-sort/selectionsort/

 

삽입 정렬

• 처음에는 왼쪽 끝의 숫자가 정렬이 되어있다고 가정합니다.
• 아직 정렬하지 않은 숫자 중에서 왼쪽 끝에 위치한 숫자를 꺼낸 후 왼쪽의 정렬된 숫자와 비교합니다.
• 왼쪽의 숫자가 크면 두 개의 숫자를 바꿉니다. 
• 이 작업을 자신보다 작은 숫자가 나타나거나 왼쪽 끝에 도달할 때까지 반복합니다.

gfycat.com/ko/densebaggyibis

 

 

힙 정렬

• 힙에 모든 숫자를 저장합니다. 힙은 내림차순으로 구축합니다. (max Heap)
• 힙에서 하나씩 꺼내면서 역순으로 정렬합니다.

hyoeun-log.tistory.com/entry/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-Heap?category=863968

[자료구조] Heap

https://commons.wikimedia.org/wiki/File:Heap_sort_example.gif

 

병합 정렬

• 수열을 반씩 분할해나갑니다. (하나의 원소만 남을 때까지)
• 그 다음 분할한 그룹을 병합해나갑니다.
• 병합할 때에는 병합 후의 그룹 내에서 오름차순으로 정렬되도록 합니다.
• 3개 이상의 숫자를 포함하고 있는 숫자를 비교하는 경우, 선두의 숫자를 비교해서 작은 숫자를 이동합니다.
• 그룹 병합 작업은 모든 숫자가 하나의 그룹으로 병합될 때까지 재귀적으로 반복합니다.

https://velog.io/@emily0_0/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Merge-Sort

 

퀵 정렬

• 정렬의 기준이 되는 수자를 하나 선택합니다. 이 숫자를 pivot이라 부릅니다.
• 피봇은 하나의 숫자를 랜덤으로 선택하는 것입니다. 편의상 가장 오른쪽의 있는 숫자를 피봇으로 선택한다고 가정하겠습니다.
• 가장 왼쪽 수에 왼쪽 마커, 오른쪽 수에 오른쪽 마커를 표시합니다.
• 왼쪽 마커를 피봇 이상인 수에 도착할 때까지 오른쪽으로 움직입니다.
• 오른쪽 마커를 피봇 미만인 수에 도착할 때까지 왼쪽으로 움직입니다.
  • 만약 왼쪽으로 움직이다 왼쪽 마커와 만나는 경우 움직임을 멈춥니다.
• 좌우 마커가 멈춘 시점에 왼쪽 마커 != 오른쪽 마커인 경우, 왼쪽 마커의 숫자와 오른쪽 마커의 숫자를 교환합니다.
  • 이후 다시 왼쪽 마커와 오른쪽 마커를 움직입니다.
• 왼쪽 마커 == 오른쪽 마커인 경우, 해당 수를 피봇과 교체합니다.
  • 이 후 피봇 기준 왼쪽 영역과 오른쪽 영역 각각에 대해 위 과정을 재귀적으로 반복합니다.

• 퀵 정렬이 최악인 경우?
  
  • 이미 정렬이 되어있는 경우
    • pivot으로 가장 큰 값 혹은 가장 작은 값이 계속 뽑히면 데이터가 분할되지 못하므로 O(n^2)