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

💎 DataStructure, Algorithm

˚₊✩‧₊ 📍 정렬이란? (정렬 종류, 원리, 비교) ˚₊✩‧₊

HYEJU01 2024. 5. 19. 13:16

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

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

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

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

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

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

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

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

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

저작자표시 비영리 변경금지