C++로 작성한 정렬 정리1 (선택,버블,삽입,퀵,병합)

       중요한 부분 / 정리

 

 

 

선택 정렬

*설명 - 남은 배열값들중 최솟값을 찾아 맨앞으로 보내 순차적으로 정렬하는 방식

(서칭한뒤 정렬,,,,본래 처음 미니멈은 9999대신 int의 최댓값을 넣음-INT_MAX)

 

*작동원리 

파란색 - 배열위치확정,,,,,빨간색-범위내에서 가장 작은 값 서칭

1,10,5,8,7,2,4,3,6,9

1,10,5,8,7,2,4,3,6,9

1,10,5,8,7,2,4,3,6,9

1,10,5,8,7,2,4,3,6,9

1,2,10,5,8,7,4,3,6,9

1,2,10,5,8,7,4,3,6,9

.....

1,2,3,4,5,6,7,8,9,10

 

이때 비교연산은

10+9+8+...+2+1,,,,,,,,,,,,(10개중 최솟값 서치,9개중 서치...)

=(10+1)+(9+2)+...(6+5)

=10*(10+1)/2

->n(n+1)/2

따라서 시간복잡도는 O(N^2)

 

 

 

버블 정렬

*설명 - 앞에서부터 차례대로 2개씩 비교하면서 매번 큰값을 찾아 뒤로 보내 역순으로 정렬하는 방식

(조건에 부합하다면 서칭하면서 계속 바꿔준다.-->>바꿔주는 동작때문에 효율 꽝)

 

*작동원리

파란색 - 배열위치확정,,,,,빨간색-범위내에서 서칭(조건에 맞다면 위치변경)

1,10,5,8,7,2,4,3,6,9

1,10,5,8,7,2,4,3,6,9

1,10,5,8,7,2,4,3,6,9,,,,,,,,(1,10에서 )

1,5,10,8,7,2,4,3,6,9

1,5,10,8,7,2,4,3,6,9

1,5,8,10,7,2,4,3,6,9

1,5,8,10,7,2,4,3,6,9

.....

1,5,8,7,2,4,3,6,9,10

.....

1,5,7,2,4,3,6,8,9,10

.....

1,2,3,4,5,6,7,8,9,10

 

이때 비교연산은

10+9+8+...+2+1,,,,,,,,,,,,(10개에서 큰값 정리,9개중 정리...)

=(10+1)+(9+2)+...(6+5)

=10*(10+1)/2

->n(n+1)/2

따라서 시간복잡도는 O(N^2)

 

 

 

삽입 정렬

*설명 - 비교 대상을 늘려가며 2개씩 비교하면서 매번 작은값을 앞으로보내 순차적으로 정렬하는 방식(이때 비교시 바꿀필요가 없다면 나머지 비교를 생략하는 방식-->>적절한 위치로 보내기)

( 주의*) 버블정렬과 비슷하지만 전혀 다른점 - 버블정렬은 n개->(n-1)개->...이런식으로 어떻든간에 일정하게 정해진대로 비교하지만 삽입정렬은 앞서 정렬한 앞부분이 순차적으로 정렬되어있다는 가정하에 뒤에 있는 수가 앞에 있는 수보다 크다면 바로 다음 차례로 넘어가 쓸데없는 연산 부분을 생략할 수 있다. )

 

*작동원리

파란색 - 배열위치확정(적절한 위치 배치를 위해 마지막 빼고는 쓰이지 않는다),,,,,빨간색-범위내에서 서칭(조건에 맞다면 위치변경)

1,10,5,8,7,2,4,3,6,9

1,10,5,8,7,2,4,3,6,9,,,,,,[0][1]비교

1,10,5,8,7,2,4,3,6,9,,,,,,[1][2]비교

1,5,10,8,7,2,4,3,6,9,,,,,,[1][2]위치변경

1,5,10,8,7,2,4,3,6,9,,,,,,[0][1]비교

1,5,10,8,7,2,4,3,6,9,,,,,,[2][3]비교

1,5,8,10,7,2,4,3,6,9,,,,,,[2][3]변경

1,5,8,10,7,2,4,3,6,9,,,,,,[1][2]비교

([2]가 [1]보다 크다 따라서 [0][1]비교는 생략하고 다음 차례로 넘어간다.)

1,5,8,10,7,2,4,3,6,9,,,,,[3][4]비교

.....

1,2,3,4,5,6,7,8,9,10

1,2,3,4,5,6,7,8,9,10

 

이때 비교연산은

10+9+8+...+2+1,,,,,,,,,,,,(10개에서 큰값 정리,9개중 정리...)

=(10+1)+(9+2)+...(6+5)

=10*(10+1)/2

->n(n+1)/2

따라서 시간복잡도는 O(N^2)

 

BUT 특수한 경우 시간복잡도가 달라지는데

앞에서 말한 생략부분이 잘들어간 경우...

예를들어 배열이 이미 어느정도 정리되어있을 경우...

즉, 배열이 2,3,4,5,6,7,8,9,10,1 같은 경우

이때는

작동원리가

2,3,4,5,6,7,8,9,10,1

2,3,4,5,6,7,8,9,1,10

...

2,1,3,4,5,6,7,8,9,10

1,2,3,4,5,6,7,8,9,10

1,2,3,4,5,6,7,8,9,10

와 같이 되어

n번 비교로 끝날 수 있다.

그러므로 이미 어느정도 정리된 배열이라면 삽입정렬이 가장 빠르다.

 

 

 

퀵 정렬

*설명 - 특정한 값(피벗)을 기준으로 작은 값, 큰 값으로 나누어 기준보다 작은 값들을 왼쪽에 기준보다 큰 값들을 오른쪽에 두는 식으로 정리하는 것을 반복(재귀)하여 정렬하는 방식

(재귀를 사용하기때문에 벗어나는 부분을 유의깊게 봐야한다,,,,,피벗값은 순차적으로 변경한다.)

 

*작동원리

파란색 - 배열위치확정,,,,,빨간색-피벗값 기준으로 범위내의 값들 정리(조건에 맞다면 위치변경),,,,,노란색-피벗값(기준값)

1,10,5,8,7,2,4,3,6,9

1,10,5,8,7,2,4,3,6,9

1,10,5,8,7,2,4,3,6,9

1,10,5,8,7,2,4,3,6,9

1,5,8,7,2,4,3,6,9,10

1,5,8,7,2,4,3,6,9,10

1,5,8,7,2,4,3,6,9,10

1,5,4,3,2,8,7,6,9,10,,,,,내부에서 조건(피벗기준)에 맞게 계속 정리된다.

1,2,4,3,5,8,7,6,9,10,,,,,정리가 됬다면 피벗을 옮긴다.

1,2,4,3,5,8,7,6,9,10

1,2,4,3,5,8,7,6,9,10

...

1,2,3,4,5,6,7,8,9,10

 

이때 비교연산은

N=2^k라고 가정한다면

배열이 균등하게 되었을경우

순환호출의 깊이는 k가 되고

피벗을 올바른 위치로 가기위한 비교연산이 평균 N번 이루어진다.

따라서 시간복잡도는 O(kN)

->O(NlogN)

 

BUT 특수한 경우 시간복잡도가 달라지는데

이미 어느정도 정렬된 배열의 경우

즉, 1,2,3,4,5,6,7,8,9,10 같은 경우

1,2,3,4,5,6,7,8,9,10

1,2,3,4,5,6,7,8,9,10

1,2,3,4,5,6,7,8,9,10

...

1,2,3,4,5,6,7,8,9,10

와 같이 되어

순환호출의 깊이가 N이 되기 때문에

시간복잡도가 O(N^2)가 된다.(최악의 경우)

 

 

 

병합 정렬

*설명 - 정렬할 배열의 값이 몇개든 무조건 반으로 나눠 개별단위까지 분해한후 2묶음씩 비교해서 정렬하는 방식

(number는 배열 값의 수,,,,,배열이 4개 라면 0시작 3끝나므로 mergeSort(array,0,3) )

 

*작동원리

파란색 - (마지막까지 바뀔 수 있기 때문에 마지막빼고는 확정짓지 않는다)배열위치확정,,,,,빨간색-비교하면서 합치기

1,8,5,7,6,2,4,3

1,  8,  5,  7,  6,  2,  4,  3

1,8,  5,7,  2,6,  3,4

1,8,  5,7,  2,6,  3,4

1,5,8,7,  2,3,4,6

1,5,8,7,  2,3,4,6

1,2,3,4,5,6,7,8

1,2,3,4,5,6,7,8

1,2,3,4,5,6,7,8

이때 비교연산은 아래의 그림을 보면 이해가 훨씬 쉽다.

해당 그림을 보면 나뉘어져 있는 배열들을 합치는 과정에서

정렬하면서 합치는데 이때 N번 비교를 하면서 합치게 된다.

또한 그러한 과정을 logN번 반복하게 되므로(퀵 정렬의 순환호출 깊이k와 같은 원리)

시간복잡도가 O(N*logN)이 된다.(퀵 정렬과 다르게 한쪽에 치우침 없이 무조건 반으로 나눈다는 방식때문에 N*logN이 보장된다.)

 

ps. 퀵 정렬 병합정렬 모두 N이 2의 거듭제곱이라는 가정하에 시간복잡도들을 계산 한것이지만 평균적으로

근접한 값이 나오기 때문에 설명하기 쉽도록 2의 거듭제곱을 예시로 활용하였다.

 

 

정리 끝

 

 

//참고자료는 각 부분

 

 

 

잘못된 정보 말씀해주시면 수정합니다. 읽어주셔서 감사합니다.