정렬

정렬

정렬을 이용하는 과정에서 최댓값과 최솟값을 구할 수 있다.

최댓값과 최솟값을 구하는 방법을 알아두면 유용하다.

 

순차정렬

• 반복적인 방법으로 해결하는 알고리즘이다.
• 배열의 가장 앞에서부터 작은 원소를 배치하는 방법이다.

#include <stdio.h> void swap(int, int); int main() { int arr[10] = { 10, 3, 4, 2, 6, 5, 8, 1, 9, 8 }; int size = sizeof(arr) / sizeof(int); for (int i = 0; i < size; i++) { for (int j = i; j < size; j++) { if (arr[j] < arr[i]) swap(&arr[j], &arr[i]); } } for (int k = 0; k < size; k++) printf("%d, ", arr[k]); return 0; } void swap(int *a, int *b) { int temp; temp = *a; *a = *b; *b = temp; }

 

버블정렬

• 반복적인 방법으로 해결하는 알고리즘이다.
• 이웃하는 두수를 비교하여 위치를 교환하는 것을 반복한다.
• 정렬할 원소의 개수를 1 줄인 후에 다시 반복

#include <stdio.h> void swap(int, int); int main() { int arr[10] = { 10, 3, 4, 2, 6, 5, 8, 1, 9, 7 }; int size = sizeof(arr) / sizeof(int); for (int i = size; i > 0; i--) { for (int j = 0; j < i-1; j++) { if (arr[j] > arr[j+1]) swap(&arr[j], &arr[j+1]); } } for (int k = 0; k < size; k++) printf("%d ", arr[k]); return 0; } void swap(int *a, int *b) { int temp; temp = *a; *a = *b; *b = temp; }

 

선택정렬

• 가장 작은 값을 맨 뒤의 원소와 교체하는 방법을 반복
• (== 가장 큰 값을 맨 앞의 원소와 교체하는 방법을 반복)

#include <stdio.h> void swap(int, int); int main() { int arr[10] = { 0, }; int min; int size = sizeof(arr) / sizeof(int); for (int i = 0; i < 10; i++) scanf("%d", &arr[i]); for (int i = size - 1; i > 0; i--) { min = i; for (int j = i; j >= 0; j--) { if (arr[j] > arr[min]) min = j; } if (i != min) swap(&arr[i], &arr[min]); } for (int k = 0; k < size; k++) printf("%d ", arr[k]); return 0; } void swap(int *a, int *b) { int temp; temp = *a; *a = *b; *b = temp; }

 

삽입정렬

1. key 원소를 따로 빼놓는다.
2. key 원소를 왼쪽 원소들과 비교해나간다.
3. 만약 key원소보다 해당 원소가 크면 오른쪽으로 옮긴다.
4. 해당 원소가 key원소보다 작으면 오른쪽으로 옮기고 남은 자리에 key값을 넣는다.
5. 반복

 

• 반복적인 방법으로 해결하는 알고리즘이다.
• 정렬 범위를 넓혀 나가는 방식으로 정렬하는 알고리즘이다.
• 새로운 범위에 포함하는 마지막 원소를 앞으로 이동하면서 자신보다 작은 원소를 찾을 때까지 자리를 교환.

#include <stdio.h> void swap(int, int); int main() { int arr[10] = { 10, 3, 4, 2, 6, 5, 8, 1, 9, 7 }; int key, j; int size = sizeof(arr) / sizeof(int); for (int i = 1; i < size; i++) { key = arr[i]; for (j = i-1; j >= 0; j--) { if (arr[j] > key) arr[j + 1] = arr[j]; else break; } arr[j + 1] = key; } for (int k = 0; k < size; k++) printf("%d ", arr[k]); return 0; }

쉘 정렬

• 삽입 정렬 알고리즘을 보완한 방법
• 같은 간격에 있는 원소들을 삽입정렬 원리로 정렬
• 간격의 초기값은 배열크기의 ½
• 간격이 1일 때 까지 ½ 씩 줄이면서 반복

 

퀵 정렬

• 재귀적인 방법으로 문제를 해결하는 알고리즘
• 가장 빠른 방법이다!
• 피벗 값을 선택하여 피벗 값보다 작은 값들은 왼쪽으로, 큰 값들은 오른쪽으로 보낸 후에 이 사이에 피벗을 위치시키는 원리

 

합병 정렬

• 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략
• 배열을 작은 단위의 배열로 분할한 후 분할한 배열을 정렬하고 이들을 다시 정렬하면서 전체 배열을 정렬하는 알고리즘.
• 분할 정복 알고리즘이다.

 

 

힙 정렬

- 힙 트리를 이용하는 알고리즘

• 최대 힙을 사용하면 크기 순으로 정렬한다.
• 최소 힙을 사용하면 크기 역순으로 정렬한다.

 

 

달팽이배열 예제

#include <stdio.h> int main() { int arr[5][5] = { 0, }; int x = -1, y = 0, nCounter = 0; int nLength = 9, nDirection = 1; for (nLength = 9; nLength > 0; nLength -= 2) { for (int i = 0; i < nLength; i++) { if (i < nLength / 2 + 1) x += nDirection; else y += nDirection; arr[y][x] = ++nCounter; } nDirection = -nDirection; } for (int i = 0; i < 5; i++) { for (int j = 0; j < 5; j++) printf("%2d  ", arr[i][j]); putchar('\n'); } return 0; }

 

 

*출처달것