[정렬] 기본 정렬 알고리즘(선택/버블/삽입)

정렬이란?

원소들을 순서대로 배열하는 것

 

수행시간에 따라 나눈 정렬 알고리즘

 

 

선택 정렬 (Selection Sort)

1. 전체 배열에서 최솟값(또는 최댓값)을 찾습니다.
2. 이 최솟값을 배열의 맨 앞에 위치시킵니다.
3. 맨 앞의 요소를 정렬된 부분으로 간주하고, 나머지 부분에 대해 같은 과정을 반복합니다.

특징:

• 시간 복잡도: O(n2)
• 공간 복잡도: (1)O(1) (제자리 정렬)
• 불안정 정렬: 동일한 값의 원소가 원래 순서를 유지하지 않을 수 있음

 

 

버블 정렬 (Bubble Sort)

1. 배열을 순회하면서 인접한 요소를 비교합니다.
2. 만약 순서가 잘못되어 있다면, 인접한 요소를 교환합니다.
3. 이 과정을 배열이 정렬될 때까지 반복합니다.

특징:

• 시간 복잡도: O(n2)
• 공간 복잡도: O(1) (제자리 정렬)
• 안정 정렬: 동일한 값의 원소는 원래 순서를 유지함

 

 

 

삽입 정렬 (Insertion Sort)

1. 배열의 각 요소를 차례대로 정렬된 부분에 삽입합니다.
2. 삽입할 요소를 선택하고, 이를 정렬된 부분의 올바른 위치로 이동시킵니다.
3. 모든 요소가 삽입될 때까지 이 과정을 반복합니다.

특징:

• 시간 복잡도: O(n2), 하지만 거의 정렬된 데이터에 대해서는 매우 효율적
• 공간 복잡도: (1)O(1) (제자리 정렬)
• 안정 정렬: 동일한 값의 원소는 원래 순서를 유지함

 

 

세 알고리즘 모두 최악의 경우 O(n2)의 시간 복잡도를 가지지만, 작은 데이터 세트에 대해서는 간단하고 효율적.

그러나 데이터가 많아질수록 더 효율적인 정렬 알고리즘들(예: 퀵 정렬, 병합 정렬)이 선호됨.

 

 

참고자료 : 「쉽게 배우는 자료구조 with 자바」