📍 정렬이란? (정렬 종류, 원리, 비교)

📍 정렬(sorting) 이란? 

• 정렬 ( sorting)  : 크기순으로 오름차순 (ascending order) , 내림차순 (descending) 으로 나열하는 것
  (서로 비교만 가능하다면 정렬할 수 있다.)

 

• 레코드 (record) : 정렬 시켜야할 대상 (학생)
• 필드 (field) : 단위 (이름,학번,주소,연락처)
• 키 (Key) : 레코드와 레코드를 식별해주는 역할을 하는 필드 (학번)

 

📍 정렬 알고리즘에 대하여 

• 정렬 알고리즘의 효율성 평가 기준  : 비교 연산 횟수, 이동 연산 횟수 

 

• 1) 단순하지만 비효율적 : 삽입 정렬, 선택 정렬, 버블 정렬 등 (데이터가 적을 때 사용)
• 2) 복잡하지만 효율적 : 퀵 정렬, 히프 정렬, 합병 정렬, 기수 정렬 등 (데이터가 많을 때 사용)

 

• 1) 내부 정렬 : 정렬 전 모든 데이터가 메인 메모리에 올라와있음
• 2) 외부 정렬 : 일부 데이터만 메모리에 올라와있음

---

⭐ 선택정렬(selection sort)  

• 선택정렬(selection sort) : 최소값을 찾아서 첫번째 요소와 교환하고, 첫번째 요소를 제외한 나머지 요소들 중에서 최소값을 찾아서 두번째 요소와 교환하는 정렬 방법 ( 정렬부분, 정렬되지않은 부분 )
• 제자리 정렬(in-place sorting) : 입력 배열 이외에 다른 추가 메모리를 요구하지 않는 정렬 방법

for i<-0 to n-2 do // n-2까지 (마지막값은 정렬 안해도 이미 큰 값)
	least <- A[i], A[i+1] .... , A[n-1] 작은값 인덱스;
    A[i] 와 A[least] 교환
    i++

 

 

---

⭐ 삽입 정렬 (insertion sort) 

• 삽입 정렬 (insertion sort) : 정렬 되지 않은 부분의 첫번째 숫자를 정렬된 부분의 어느 위치에 삽입해야하는지 판단하고 삽입한다. 이후 정렬부분 크기는 증가하고 정렬되지않은 부분 크기는 줄어든다.( 정렬부분, 정렬되지않은 부분 )
• 대부분 정렬되어 있는 경우 매우 효율적
• 삽입 정렬 복잡도 :  (최악) 입력자료가 역순일때

for i<-1 to n-1 do
	key<-A[i];
    j <- i+1
    while j>=0 and A[j] > key do
    	A[j+1] <- A[j]
        j <- j+1
    A[j+1] <- key

---

⭐ 버블 정렬 (bubble sort) 

• 버블 정렬 (bubble sort) : 인접한 2개 레코드를 비교하여 크기가 순서대로 되어 있지 않으면 서로 교환한다. 가장 큰 값이 리스트의 오른쪽 끝으로 이동하게 되고 계속 반복한다. (비교-교환 과정) 
• 문제점 : 순서에 맞지 않은 요소를 인접한 요소와 교환한다, 모든 다른 요소들과 교환되어야 함.
• 교환 작업이 이동 작업보다 복잡해서 잘 쓰이지 않음

for i<-n-1 to i do
	for j<-0 to i-1 do
    	j와 j+1번째의 요소가 크기 순이 아니면 교환
        j++
   i--

 

---

⭐ 쉘 정렬 (shell sort)

• 쉘 정렬 (shell sort) : Donald L. Shell 이라는 사람이 제안한 방법, 삽입 정렬이 어느정도 정렬된 배열에 대해서 빠른 것에 대하여 착안한 방법이다. 간격(갭)을 두고 여러개의  부분 리스트를 만들고, 각 부분리스트에 삽입 정렬을 이용하여 정렬한다. 첫번째 패스가 끝나면 간격을 1/2 줄여서 다시 부분 리스트를 만들고 과정을 반복한다. 부분 리스트 개수가 1개가 될 때까지 반복한다. (부분리스트 생성 - 부분리스트정렬) 
• 장점:  자료의 교환 시 더 큰 거리를 이동 가능하다 , 부분리스트는 어느정도 정렬 상태이기 때문에 삽입정렬을 수행하는 것임에도 빠르게 수행된다.
• 삽입 정렬과 차이점 : 삽입 정렬의 경우 요소 삽입시, 이웃한 위치로만 이동된다. 삽입 위치가 먼 경우 이동이 많아진다. 하지만 쉘 정렬은 멀리 떨어진 위치로도 이동이 가능하다. 

---

⭐ 합병 정렬 (merge sort) 

• 합병 정렬 (merge sort) : 하나의 리스트를 두개의 균등한 크기로 분할하고 분할된 부분리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합한다. (분할정복기법 바탕에 두고있다.)
• Divide -> Conquer -> Combine
• 분할 정복 기법 (divide and conquer)  : 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음 결과를 모아서 원래의 문제를 해결하는 전략.
• 장점 : 안정적인 정렬 방법, 데이터 분포에 상관 없이 정렬 시간은 동일하다. 연결리스트를 사용하면 어떤 정렬보다 효율적일 수 있음
• 단점 : 임시 배열이 필요함

if left < right
    mid = left+right / 2
    merge_sort(list, left, mid)
    merge_sort(list, mid+1, right)
    merge(list, left, mid, right)

---

⭐ 퀵 정렬 (quick sort) 

• 퀵 정렬 (quick sort) : 합병 정렬과 비슷하게 진행된다 하지만 퀵정렬은 리스트를 비균등하게 분할한다. 먼저 한 요소를 피벗 (pivot) 으로 선택하고 피벗보다 작으면 왼쪽, 크면 오른쪽으로 옮긴다. 오른쪽,왼쪽 부분 리스트들을 다시 퀵정렬로 되풀이하고 분할이 불가능할때까지 진행해준다. (분할정복기법 바탕에 두고있다.)
• 시간 복잡도 : O(nlog2n)  : 불필요한 데이터 이동을 줄임, 먼거리 데이터 교환 가능, 한번 결정된 피벗들은 추후 연산에서 제외되는 특성
• 장점 : 속도가 매우 빠름, 추가 메모리 필요없음
• 단점: 이미 정렬된 리스트에 대해서 수행시간이 더 많이 걸림
• 중간 값 선택 방법 (median of three) : 불균형 분할을 방지하기 위해 왼쪽,중간,오른쪽 데이터 중 중간 값을 선택하는 방법을 많이 사용한다.

---

⭐ 히프 정렬 (heap sort) 

최대히프 정렬

• 히프 정렬 (heap sort) : 정렬할 배열을 최소 히프로 변환하여 가장 작은 원소부터 차례대로 추출하여 정렬하는 방법. 최소히프를 만들고 숫자를 차례대로 삽입한 다음 최솟값 부터 삭제하면 된다.

 

• 최소히프 : 원소의 개수 만큼 삭제 연산을 수행하여 오름차순으로 정렬
• 최대히프 : 원소의 개수 만큼 삭제 연산을 수행하여 내림차순으로 정렬  (배열의 뒤쪽부터 저장)

 

• 히프 : 우선순위 큐를 완전 이진트리로 구현하는 방법
• MAX HEAP = 최대 히프 루트 노드(키값)가 가장 큼
• MIN HEAP = 최소 히프 루트 노드(키값)가 가장 작음 

---

⭐ 기수 정렬 (radix sort) 

• 기수 정렬 (radix sort) : 레코드를 비교하지 않고 정렬하는 방법, 기수(radix) 숫자의 자리수, 자리수 값에 따라서 정렬한다. 십진수의 각 자리 수는 0~9 만 가지므로 10개의 버킷을 만들어서 각 자리수의 값에 따라 상자에 넣고 버킷 안에 들어있는 숫자를 순서대로 읽으면 정렬된 숫자를 얻을 수 있다. (다단계 정렬, 단계의 수는 데이터의 자리수의 개수와 일치한다.) 
• 장점 : 빠른 수행시간, 비교 연산을 하지 않음
• 단점 : 추가적인 메모리 필요 , 키값이 숫자로 표현되어야만 가능하다.

 

---

 

📍 정렬 비교 

 

퀵 정렬 >합병정렬>히프정렬>쉘정렬>> 삽입정렬>선택정렬> 버블정렬