📌정렬(sort)

데이터를 정해진 기준에 따라 배치해 의미 있는 구조로 재설정하는 것

04-1. 버블(bubble) 정렬

데아터의 인접 요소끼리 비교하고, 루프를 돌면서 swap 연산을 수행하며 정렬하는 방식

❗시간복잡도 O(n$^2$)

✖️버블 정렬 과정

① 비교 연산이 필요한 루프 범위를 설정한다.

② 안전한 데이터 값을 비교한다.

③ swap 조건에 부합하면 swap 연산을 수행한다.

④ 루프 범위가 끝날 때까지 ②~③을 반복한다.

⑤ 정렬 영역을 설정하고, 다음 루프를 실행할 때는 이 영역을 제외한다.

⑥ 비교 대상이 없을 때까지 ①~⑤을 반복한다.

---

04-2. 선택(selection) 정렬

대상에서 가장 크거나 작은 데이터를 데이터가 나열된 순으로 찾아가 선택을 반복하면서 정렬하는 방식

❗시간복잡도 O(n$^2$)

✖️선택 정렬 과정

① 남은 정렬 부분에서 최솟값 또는 최댓값을 찾는다.

② 남은 정렬 부분에서 가장 앞에 있는 데이터와 선택된 데이터를 swap한다.

③ 가장 앞에 있는 데이터의 위치를 변경해(index++) 남은 정렬 부분의 범위를 축소한다.

④ 전체 데이터 크기만큼 index가 커질 때까지, 즉 남은 정렬 부분이 없을 때까지 반복한다.

---

04-3. 삽입(insertion) 정렬

대상을 선택해 이미 정렬된 영역에서 정렬되지 않은 선택 데이터의 적절한 위치를 찾아 삽입하면서 정렬하는 방식

❗시간복잡도 O(n$^2$)

✖️삽입 정렬 과정

① 현재 index에 있는 데이터 값을 선택한다.

② 현재 선택한 데이터가 정렬된 데이터 범위에 삽입될 위치를 탐색한다.

③ 삽입 위치부터 index에 있는 위치까지 shift 연산을 수행한다.

④ 삽입 위치에 현재 선택한 데이터를 삽입하고 index++ 연산을 수행한다.

⑤ 전체 데이터의 크기만큼 index가 커질 때까지, 즉 선택할 데이터가 없을 때까지 반복한다.

---

04-4. 퀵(quick) 정렬

기준값 pivot을 선정해 해당 값보다 작은 데이터와 큰 데이터로 분류하는 것을 반복해 정렬하는 알고리즘

❗시간복잡도 평균: O(nlogn) 최악: O(n$^2$)

✖️퀵 정렬 과정

① 데이터를 분할하는 pivot을 설정한다.

② pivot을 기준으로 다음 a~e 과정을 거쳐 데이터를 2개의 집합으로 분리한다.

②-a start가 가리키는 데이터가 pivot이 가리키는 데이터보다 작으면 start를 오른쪽으로 1칸 이동한다.

②-b end가 가리키는 데이터가 pivot이 가리키는 데이터보다 크면 end를 왼쪽으로 1칸 이동한다.

②-c start가 가리키는 데이터가 pivot이 가리키는 데이터보다 크고, end가 가리키는 데이터가 pivot이 가리키는 데이터보다 작으면 start, end가 가리키는 데이터를 swap하고 start는 오른쪽, end는 왼쪽으로 1칸씩 이동한다.

②-d start와 end가 만날 때까지 ②-a~②-c를 반복한다.

②-e start와 end가 만나면 만난 지점에서 가리키는 데이터와 pivot이 가리키는 데이터를 비교하여 pivot이 가리키는 데이터가 크면 만난 지점의 오른쪽에, 작으면 만난 지점의 왼쪽에 pivot이 가리키는 데이터를 삽입한다.

③ 분리 집합에서 각각 다시 pivot을 설정한다.

④ 분리 집합이 1개 이하가 될 때까지 과정 ①~③을 반복한다.

---

04-5. 병합(merge) 정렬

분할 정복(divide and conquer) 방식을 사용해 데이터를 분할하고 이미 정렬된 부분 집합들을 효율적으로 병합해 전체를 정렬하며 합치는 알고리즘

❗시간복잡도 O(nlogn)

✖️2개의 그룹을 병합하는 과정

① 투 포인터 개념을 사용한다.

② 왼쪽 포인터와 오른족 포인터의 값을 비교하여 작은 값을 결과 배열에 추가하고 포인터를 오른쪽으로 1칸 이동시킨다.

③ 정렬이 완료될 때까지 과정 ②를 반복한다.

---

04-6. 기수(radix) 정렬

값을 놓고 비교할 자릿수를 정한 다음 해당 자릿수만 비교하는 알고리즘

예) 234, 123 비교하면 4와 3, 3과 2, 2와 1만 비교한다.

❗시간복잡도 O(kn)

• k : 데이터의 자릿수

✖️기수 정렬 핵심 이론

• 10개의 큐를 이용, 각 큐는 값의 자릿수를 대표한다.

• 대상 데이터를 일의 자리에서 정렬된 순서 기준으로 십의 자리에 저장 하는 것이 중요!

• 데이터를 담는 자료구조는 Queue로 FIFO 형태를 취한다.