💡 정렬 (Sort)
👉 특정 값을 기준으로 데이터를 순서대로 배치하는 방법이다.
💡 정렬의 종류
👉 구현 난이도는 쉽지만, 속도는 느린 알고리즘
- 버블 정렬
- 삽입 정렬
- 선택 정렬
👉 구현 난이도는 조금 더 어렵지만, 속도는 빠른 알고리즘
- 합병 정렬
- 힙 정렬
- 퀵 정렬
- 트리 정렬
👉 하이브리드 정렬
- 팀 정렬
- 블록 병합 정렬
- 인트로 정렬
👉 기타 정렬 알고리즘
- 기수 정렬
- 카운팅 정렬
- 셸 정렬
- 보고 정렬
💡 버블 정렬
👉 인접한 데이터를 비교하며 자리를 바꾸는 방식이다.
👉 알고리즘 복잡도 : O(n²)
💡 버블 정렬 과정
- 배열의 가장 작은 인덱스 부터 두 수를 비교해서 작은 수를 왼쪽으로 큰 수를 오른쪽으로 보내서 자리를 바꿔준다.
- 같은 방식으로 마지막 인덱스까지 자리를 바꿔주면 가장 큰 수가 마지막 인덱스에 자리하게 된다.
- 끝에서부터 자리를 잡게된 수를 제외하고 횟수가 한번씩 줄게된다.
따라서 수행 횟수는 O(n²) = n(n-1)/2 가 된다.
💡 버블 정렬의 구현
👉 의사 코드 (Pseudocode)
의사코드 (Pseudo code)
: 알고리즘 flow 파악용으로 실제 돌아가는 코드는 아니다.
슈도 코드라고도 읽고, 가짜 코드라고도 한다.
bubbleSort(arr[]){
arr[SIZE]
for i=1 to SIZE-1 {
for j=0 to SIZE-i {
if(arr[j] > arr[j+1])
swap (arr[j],arr[j+1])
}
}
}💡 삽입 정렬 (Insertion Sort)
👉 앞의 데이터를 정렬 해가면서 삽입 위치를 찾아 정렬하는 방식이다.
👉 알고리즘 복잡도 : O(n²)
💡 삽입 정렬 과정
- 1번 인덱스부터 앞의 데이터와 비교해서 더 작으면 앞으로 삽입해준다.
- 인덱스를 뒤로 옮겨가면서 똑같이 비교하면서 진행한다.
- 만약 비교했는데 크면 그대로 둔다.
- 버블 정렬과는 다르게 앞의 모든 수와 비교해서 작으면 앞으로 삽입해준다.
- 마지막 인덱스까지 비교해서 정렬해준다.
따라서 수행 횟수는 O(n²) = n(n-1)/2 가 된다.
하지만 수가 큰 경우 비교를 하지 않는 경우도 발생하기 때문에 버블 정렬보다는 평균적으로 빠르다.
💡 삽입 정렬의 구현
👉 의사 코드 (Pseudocode)
insertionSort(arr[]){
arr[SIZE]
for i=1 to SIZE {
for j=i to 0 (j--) {
if(arr[j] < arr[j-1])
swap (arr[j],arr[j-1])
}
}
}💡 선택 정렬 (Selection Sort)
👉 주어진 값에서 최소 또는 최대 값을 찾아서 가장 앞 또는 뒤부터 정렬하는 방식이다.
👉 알고리즘 복잡도 : O(n²)
💡 선택 정렬 과정
- 배열에서 전체 값을 비교해가면서 최소값을 찾아서 가장 앞의 데이터와 위치를 바꿔준다.
- 남은 데이터 중에서 최소값을 찾아서 가장 앞의 데이터와 위치를 바꿔준다.
- 같은 방식으로 계속 진행해서 정렬한다.
따라서 수행 횟수는 O(n²) = n(n-1)/2 가 된다.
위 세가지 정렬은 제자리 정렬 (in-place sort) 이라고도 한다.
배열 내에서 자리만 바꿔가면서 정렬하는 방식이기 때문에 추가적인 데이터는 따로 필요하지 않다.
따라서 메모리를 최소한으로 사용하면서 정렬하는 방식이다.
💡 선택 정렬의 구현
👉 의사 코드 (Pseudocode)
insertionSort(arr[]){
arr[SIZE]
for i=0 to SIZE-1 {
min=i
for j=i+1 to SIZE {
if(arr[j] < arr[min])
min=j
}
swap (arr[i],arr[min])
}
}
BE