[자료구조] Sort 정렬

📌 정렬과 탐색

탐색

리스트 : 하나 이상의 필드로 된 레코드의 집합

키 : 레코드를 구분하기 위해서 사용되는 필드

순차탐색 : 레코드 리스트를 왼→오 또는 오→왼으로 레코드를 검사하는 것 → O(n)

이원탐색 : O(logn)

보간법에 의한 탐색 : 리스트가 정렬되었을 때만 사용 가능.

리스트를 반복해서 탐색할 때 리스트를 정렬된 상태로 유지하는 것이 이롭다

정렬

2개 이상의 자료를 오름차순이나 내림차순으로 재배열하는 것

키 : 자료를 정렬하는데 사용하는 기준이 되는 특정 값

실행 방법에 따른 분류

• 비교식 정렬 : 두개씩 비교하여 교환
• 분산식 정렬 : 여러개의 부분 집합으로 분해하고 각 부분집합을 정렬

정렬 장소에 따른 분류

• 내부 정렬 : 정렬할 자료를 메인 메모리에 올려서 정렬하는 방식. 속도빠르지만 자료의 양이 제한
• 외부 정렬 : 정렬할 자료를 보조 기억 장치에서 정렬하는 방식. 속도는 떨어지지만 대용량 자료 정렬 가능

내부 정렬 방식

• 교환 방식
• 삽입 방식
• 병합 방식
• 분배 방식
• 선택 방식

외부 정렬 방식

• 병합 방식

📌 다양한 정렬 알고리즘 - O(n^2)

$O(n^2)$

버블 정렬 : 인접한 두 개의 원소를 비교하여 자리를 교환하는 방식

n개 메모리 사용

인접한것 끼리 비교해서 교환하고 마지막 원소부터 확정해나감

선택 정렬 : 전체 원소들 중에서 기준 위치에 맞는 원소를 선택하여 자리를 교환하는 방식으로 정렬

n개 메모리 사용

최소값을 찾아서 교환해나가는 방식

삽입 정렬 : 정렬되어 있는 부분 집합에 정렬할 새로운 원소의 위치를 찾아 삽입하는 방법

n개 메모리 사용

📌 다양한 정렬 알고리즘 - O(nlogn)

$O(nlogn)$

퀵정렬

기준 값을 중심으로 왼쪽 부분 집합과 오른쪽 부분 집합으로 분할하여 정렬하는 방법

기준값 : 피봇 → 전체 원소 중 첫번째 원소 또는 가운데 원소를 선택

왼쪽 부분 집합에는 피봇보다 작은 원소들, 오른쪽 부분 집합에는 피봇보다 큰 원소들 이동시킴

divide & conquer

• 분할 : 정렬할 자료들을 2개 부분집합으로 분할
• 정복 : 기준값기준으로 정렬

변수 : left / right / low / high / pivot

1. low는 오른쪽으로 이동. 피봇보다 큰 값을 만날 때 까지 이동
2. high는 왼쪽 이동. 피봇보다 작은 값을 만날 때 까지 이동
3. low와 high가 멈추면 둘의 값을 교환
4. 교환 후에는 멈춘위치에서 부터 이동과 교환을 계속(반복)
5. high와 low가 역전되면 피벗과 high의 데이터 교환
6. 피벗 기준으로 왼쪽 / 오른쪽 부분이 나뉘어짐. 각각의 부분집합에서 위의 과정을 계속함
7. 배열의 길이가 1이나 0이될 때 까지 계속 반복

최악의 경우 : 피벗이 치우쳐 분할되었을 때 → O(n^2)

bad 분할 → 분할 중 하나의 크기가 3/4보다 클 때

병합 정렬

여러 개의 정렬된 자료의 집합을 병합하여 한 개의 정렬된 집합으로 만드는 방법

divide & conquer

최대한 1개 남을때까지 반씩 나눔.

별도의 정렬 진행하지 않아도 될 때까지 분할 후 합병

2n개의 메모리 공간 사용 → 문제점

힙 정렬

힙 자료구조를 이용한 정렬 → 힙에서는 항상 가장 큰 원소가 루트노드가 되고, 삭제시 루트 노드가 삭제되는 것을 이용

1. 원소들을 정렬하여 최대 힙 구성
2. 삭제연산을 진행하며 가장 큰 원소부터 뺌
3. 반복

완전이진트리를 힙으로 구성하는 시간 O(logn) * n개

📌 기수정렬 - O(n)

정렬할 원소의 키 값에 해당하는 버킷에 원소를 분배하였다가 버킷의 순서대로 원소를 꺼내는 방법을 반복하며 정렬

기수만큼의 버킷 사용 → ex) 10진수 → 0-9의 10개 버킷 사용

만약 두자리수 자료들을 정렬시 → ex) 10, 69 22 등…

버킷에 일의 자리 값 기준으로 넣고 순서대로 꺼냄

→ 버킷에 십의 자리 값 기준으로 넣고 순서대로 꺼냄

→ 정렬완료

n개 메모리 공간 + 기수 r에 따른 버킷공간(십진수 10, 2진수 2)

내부 정렬 요약

	최악	평균
삽입	n^2	n^2
힙	nlogn	nlogn
합병	nlogn	nlogn
퀵	n^2	nlogn

삽입 정렬 : 리스트가 부분적으로 정렬되어 있을 때 좋음. 작은 n에 대해 가장 좋은 정렬 방법

합병 정렬 : 최악의 경우에 가장 좋은 방법. 힙 정렬에 비해 많은 공간 필요

퀵 정렬 : 평균 성능이 가장 좋음. 그러나 최악의 경우 n^2

기수 정렬 : 성능이 키의 크기와 r의 선택에 영향 받음