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

정렬 : 데이터를 순서대로 나열하는 방법

1. 버블 정렬(Bubble Sort)

2. 선택 정렬(Select Sort)

3. 삽입 정렬(Insert sort)

4. 퀵 정렬(Quick Sort)

5. 머지 정렬(Merge sort)

1. 버블 정렬(Bubble sort)

매번 연속된 두 개 인덱스를 비교하여, 정한 기준의 값을 뒤로 넘겨 정렬하는 알고리즘

시간복잡도가 높아 실제로 잘 사용되지 않는 정렬

2. 선택 정렬(Selection sort)

주어진 리스트에 최소값을 찾아 맨 앞에 위치한 값과 교체하며 리스트를 반복해 교체하는 알고리즘

정렬되지 않은 배열 인덱스의 맨 앞에서부터 포함한 이후의 배열 값 중 가장 작은 값을 찾아 정렬하는 알고리즘

3. 삽입 정렬(Insertion sort)

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

4. 퀵 정렬(Quick sort)

분할 정복 알고리즘의 종류로 pivot을 선정하여 pivot을 기준으로 좌측과 우측으로 pivot보다 작은 값을 왼쪽, pivot보다 큰 값을 오른쪽으로 재배치를 하고 계속하여 분할하여 정렬하는 알고리즘

*pivot : 리스트 가운데서 고른 하나의 원소

*분할정복 : 커다란 문제를 잘게 나눠서 작은 문제를 극복

5. 머지 정렬(Merge sort)

분할 정복 알고리즘의 종류로 큰 문제를 반으로 쪼개 문제를 해결해 나가는 방식으로 배열의 크기가 1보다 작거나 같을 때까지 반복해 정렬하는 알고리즘

두 개의 배열을 비교하여, 기준에 맞는 값을 다른 배열에 저장해 나가는 방식

머지 정렬 와 퀵 정렬의 차이

병합 정렬은 정확하게 이분할을 하는 반면에 퀵 정렬의 경우에는 정확하게 이분할되지 않는 차이가 있습니다.

출처 : 생활코딩