[Algorithm] Sort(정렬)

정렬이란?

 

정렬은 어떤 데이터셋이 주어졌을 때 이를 정해진 순서대로 나열하여 재배치하는 문제이다. 종류가 많으며 그리디 문제에 쓰이는 경우가 많다.

 

정렬의 종류

• O(n²) : Insertion sort, Selection sort, Bubble sort
• O(nlogn) : Quick sort, Merge sort, Heap sort

버블정렬(Bubble sort)

• 인접한 두 원소를 비교
• 왼쪽 원소>오른쪽 원소라면 swap
• 가장 큰 원소부터 오른쪽에 정렬됨
• 데이터가 하나씩 정렬되면서 비교 대상에서 제외

합병정렬(Merge sort)

• 분할 정복 방식으로 설계된 알고리즘
• 하나의 배열을 정확히 반으로 나눔
• 나뉜 배열들을 정렬
• 다시 하나의 배열로 합치기