정렬 알고리즘(선택,삽입,버블,합병,퀵)

정렬 알고리즘:

일정한 순서대로 요소를 나열하는 알고리즘

(번호 순, 사전 순...)

선택 정렬

배열을 순회하며 최솟값을 찾고 제일 앞으로 보낸다음에 그 위치에 있는 값과 자리를 바꾼다.

단, 이미 바뀐 최솟값은 건들지 않는다.

평균 시간 복잡도: O(n의 제곱)

list = [2,5,6,8,1,3,9,4,7]



// 1과 2의 값을 바꾸기
>>>[1,5,6,8,2,3,9,4,7]


// 2와 5의 값을 바꾸기
>>>[1,2,6,8,5,3,9,4,7]
.
.
.
.
list = [1,2,3,4,5,6,7,8,9]

삽입 정렬

자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성한다.

평균 시간 복잡도: O(n의 제곱)

list = [2,5,1,8,6,3,9,4,7]

[_,2,_,5,1,8,6,3,9,4,7]
// 2는 제일 앞에 있으니 들어갈 위치가 고정되어 있다.
// 따라서 5부터 비교를 한 다음 삽입한다.
// 5의 앞에는 들어갈 자리가 이렇게 2개가 있다.
// 5는 2보다 크므로 그대로 있는다.
>>>[2,5,1,8,6,3,9,4,7]

[_,2,_,5,_,1,8,6,3,9,4,7]
//1의 앞에는 들어갈 자리가 이렇게 3개가 있다.
//1은 5보다 작고 2보다도 작으므로 
>>>[1,2,5,8,6,3,9,4,7]
//제일 앞에 들어간다.
.
.
.
list = [1,2,3,4,5,6,7,8,9]

버블 정렬

서로 인접한 두 원소를 검사하여 정렬한다.

평균 시간 복잡도: O(n의 제곱)

list = [5,2,7,3,1]
//1. 5를 2와 비교하여 교환
>>>[2,5,7,3,1]
//2. 5를 7과 비교하여 교환(X)
>>>[2,5,7,3,1]
//3. 7을 3과 비교하여 교환
>>>[2,5,3,7,1]
//4. 7을 1과 비교하여 교환
>>>[2,5,3,1,7]
.
.
.
list = [1,2,3,5,7]

합병 정렬

분할 후 분할한 리스트를 서로 비교한 후 하나의 리스트를 만든다.

평균 시간 복잡도: O(nlogn)

참고: https://reakwon.tistory.com/38

퀵 정렬

랜덤으로 요소 중에 'pivot'이라는 값을 정하고

pivot보다 작은 값은 pivot의 왼쪽에,

pivot보다 큰 값은 pivot의 오른쪽에 정렬한다.

평균 시간 복잡도: O(nlogn)

참고: https://spacebike.tistory.com/29