정렬 알고리즘 알아보기

💡 정렬 알고리즘

📍 퀵 정렬(Quick Sort)

• 퀵 정렬은 피벗을 두고 피벗의 왼쪽에서 피벗보다 작은 값을 오른쪽에는 큰 값을 두는 과정을 반복하는 알고리즘이다.
• 레코드의 많은 자료 이동을 없애고 하나의 파일을 부분적으로 나누어 가면서 정렬한다.

https://utf-404.tistory.com/54

Quick Sort 구현(Java)

 

📍 합병 정렬(Merge Sort)

• 합병 정렬은 전체 원소를 하나의 단위로 분할한 후 분할한 원소를 다시 합병해서 정렬하는 알고리즘이다.

https://utf-404.tistory.com/53

Merge Sort 구현(Java)

 

📍 힙 정렬(Heap Sort)

• 힙 정렬은 정렬한 입력 레코드들로 힙을 구성하고 가장 큰 키값을 갖는 루트 노드를 제거하는 과정을 반복하여 정렬하는 알고리즘이다.
• 완전이진 트리(Complete Binary Tree)로 입력 자료의 레코드를 구성한다.
• 힙 정렬의 수행시간은 다음과 같다

최악 시간복잡도	O(n log n)
최선 시간복잡도	O(n log n)
평균 시간복잡도	O(n log n)
공간복잡도	O(1)

 

📍 거품 정렬(Bubble Sort)

• 거품 정렬은 인접한 2개의 레코드 키값을 비교하여 그 크기에 따라 레코드 위치를 서로 교환하는 알고리즘이다.
• 두 인접한 원소를 교환하는 과정이 거품 모양과 같다고 하여 거품 정렬이라고 이름이 지어졌다.
• 한 PASS를 수행할 때마다 가장 큰 값이 맨 뒤로 이동하기 때문에, PASS를 '요소의 개수-1'번 수행하게 되면 모든 숫자가 정렬된다.

<참고 자료>

거품 정렬 이미지로 보기

 

 

📍 삽입 정렬(Insertion Sort)

• 삽입 정렬은 2번째 키와 첫 번째 키를 비교하여 순서대로 나열하고, 이어서 3번째 키를 1, 2번째 키와 비교해 순서대로 나열하고, 계속해서 n번째 키를 앞의 (n-1) 개 키와 비교하여 알맞은 순서에 삽입하는 알고리즘이다.
• 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다.

<참고 자료>

삽입 정렬 이미지로 보기

 

📍 선택 정렬(Selection Sort)

• 선택 정렬은 정렬되지 않은 데이터들에 대해 가장 작은 데이터를 찾아 정렬되지 않은 부분의 가장 앞의 데이터와 교환해 나가는 알고리즘이다.

<참고 자료>

선택 정렬 이미지로 보기