영권's
정렬 1 (선택 정렬, 버블 정렬) 본문
정렬이란?
• 주어진 자료들을 어떤 기준에 의하여 크기 순서대로 나열한 것
• 정렬 알고리즘의 핵심 요소는 교환, 선택, 삽입이며 대부분의 정렬 알고리즘은 이 세가지 요소를 응용한 것입니다.
• 데이터를 정렬해야 하는 이유는 탐색을 효율적으로 하기 위해서 입니다.
선택 정렬
선택 정렬 : 잘못된 위치에 들어가 있는 원소를 찾아 그것을 올바른 위치에 집어넣는 원소 교환으로 정렬을 하는 방법이다.
그래서 먼저 작은 원소를 찾아 첫 번째 위치에 있는 원소와 교환하고 다음에는 두 번째로 작은 원소를 찾아 두 번째 위치에 있는 원소와 교환한다. 이렇게 매번 나머지(a[i] ... a[n-1]) 원소 중에서 가장 작은 원소를 찾아 a[i] 원소와 교환하는 작업을 모든 원소가 올바른 위치에 있게 될 때까지 계속하면 원하는 오름차순 정렬이 된다.
package chap06;
import java.util.Scanner;
// 단순 선택 정렬
class SelectionSort {
// 배열 요소 a[idx1]과 a[idx2]의 값을 바꿉니다.
static void swap(int[] a, int idx1, int idx2) {
int t = a[idx1]; a[idx1] = a[idx2]; a[idx2] = t;
}
// 단순 선택 정렬
static void selectionSort(int[] a, int n) {
for (int i = 0; i < n - 1; i++) {
int min = i; // 아직 정렬되지 않은 부분에서 가장 작은 요소의 인덱스를 기록합니다.
for (int j = i + 1; j < n; j++)
if (a[j] < a[min])
min = j;
swap(a, i, min); // 아직 정렬되지 않은 부분의 첫 요소와 가장 작은 요소를 교환합니다.
}
}
public static void main(String[] args) {
Scanner stdIn = new Scanner(System.in);
System.out.println("단순 선택 정렬");
System.out.print("요솟수：");
int nx = stdIn.nextInt();
int[] x = new int[nx];
for (int i = 0; i < nx; i++) {
System.out.print("x[" + i + "]：");
x[i] = stdIn.nextInt();
}
selectionSort(x, nx); // 배열x를 단순선택정렬
System.out.println("오름차순으로 정렬했습니다.");
for (int i = 0; i < nx; i++)
System.out.println("x[" + i + "]＝" + x[i]);
}
}
버블 정렬
버블 정렬은 배열을 검사하여 두 인접한 원소가 정렬 순서에 맞지 않으면 이들을 서로 교환하고 이것을 반복한다.
즉, 먼저 a[0]과 a[1]을 비교하여 정렬 순서에 맞지 않으면 서로 교환한다.
다음 a[1]과 a[2]를 다시 비교하여 순서에 맞지 않으면 교한하는데 이 과정을 a[n-2]와 a[n-1]이 될 때까지 반복한다.
이렇게 하면 가장 큰 원소가 배열의 n-1위치로 끌어 오르게(bubbled up) 된다.
그러나 이것은 배열 전체에 대한 첫 번째 패스이며 이 정렬은 다시 배열 처음부터 인접한 원소를 비교하여 순서가 맞지 않으면 교환하면서 검사하게 되는데 이 때는 마지막 비교가 a[n-3]과 a[n-2]가 된다.
왜냐하면 제일 큰 원소는 이미 위치 n-1에 선정되어 있기 때문이다.
이 과정은 마지막 패스로 a[0]과 a[1]을 비교하여 순서가 맞지 않으면 서로 교환할 때까지 계속한다.
버블 정렬 코드
package chap06;
import java.util.Scanner;
// 버블 정렬(버전 1)
class BubbleSort {
// a[idx1]와 a[idx2]의 값을 바꿉니다.
static void swap(int[] a, int idx1, int idx2) {
int t = a[idx1];
a[idx1] = a[idx2];
a[idx2] = t;
}
// 버블 정렬
static void bubbleSort(int[] a, int n) {
for (int i = 0; i < n - 1; i++)
for (int j = n - 1; j > i; j--)
if (a[j - 1] > a[j])
swap(a, j - 1, j);
}
public static void main(String[] args) {
Scanner stdIn = new Scanner(System.in);
System.out.println("버블 정렬(버전 1)");
System.out.print("요솟수：");
int nx = stdIn.nextInt();
int[] x = new int[nx];
for (int i = 0; i < nx; i++) {
System.out.print("x[" + i + "]：");
x[i] = stdIn.nextInt();
}
bubbleSort(x, nx); // 배열 x를 버블 정렬합니다.
System.out.println("오름차순으로 정렬했습니다.");
for (int i = 0; i < nx; i++)
System.out.println("x[" + i + "]＝" + x[i]);
}
}버블 정렬의 시간복잡도
비교 횟수
- 최상, 평균, 최악 모두 일정
- n-1, n-2, ... 2, 1 번 = n(n-1)/2
교환 횟수
- 입력 자료가 역순으로 정렬 되어 있는 최악의 경우, 한 번 교환하기 위하여 3번의 이동(SWAP 함수의 작업)이 필요하므로 (비교 횟수 *3 )번 = 3n(n-1) /2
- 입력 자료가 이미 정렬 되어 있는 최상의 경우, 자료의 이동이 발생하지 않는다.
T(n_ = O(n^2)
알고리즘 개선(1)
사진에서 세번째 패스가 마치고 나면 4가 3번째 자리에 위치합니다.
사진은 네번째 패스로 여기서는 요소의 교환이 한번도 이루어 지지 않습니다. 왜냐하면 이미 세 번째 패스에서 정렬이 끝났기 때문입니다.
즉, 어떤 패스에서 요소의 교환 횟수가 0이면 더 이상 정렬할 요소가 없다는 뜻이기 때문에 정렬 작업을 멈추면 됩니다.
만약 처음부터 정렬이 되어있는 배열이라고 가정하면 첫번째 패스에서 교환이 수행되지 않으므로 첫 번째 패스를 마친 다음에 정렬 작업을 마치게 됩니다.
다음 코드는 이런 '멈춤'으로 개선한 버블 정렬 코드 입니다.
package chap06;
import java.util.Scanner;
// 버블 정렬(버전 2)
class BubbleSort2 {
// 배열 요소 a[idx1]과 a[idx2]의 값을 바꿉니다.
static void swap(int[] a, int idx1, int idx2) {
int t = a[idx1]; a[idx1] = a[idx2]; a[idx2] = t;
}
// 버블 정렬(버전 2)
static void bubbleSort(int[] a, int n) {
for (int i = 0; i < n - 1; i++) {
int exchg = 0; // 패스의 교환 횟수를 기록합니다.
for (int j = n - 1; j > i; j--)
if (a[j - 1] > a[j]) {
swap(a, j - 1, j);
exchg++;
}
if (exchg == 0) break; // 교환이 이루어지지 않으면 종료합니다.
}
}
public static void main(String[] args) {
Scanner stdIn = new Scanner(System.in);
System.out.println("버블 정렬(버전 2)");
System.out.print("요솟수：");
int nx = stdIn.nextInt();
int[] x = new int[nx];
for (int i = 0; i < nx; i++) {
System.out.print("x[" + i + "]：");
x[i] = stdIn.nextInt();
}
bubbleSort(x, nx); // 배열 x를 단순교환정렬
System.out.println("오름차순으로 정렬했습니다.");
for (int i = 0; i < nx; i++)
System.out.println("x[" + i + "]＝" + x[i]);
}
}
알고리즘 개선(2)
다음 사진은 버블 정렬의 첫 번째 패스의 비교, 교환 과정을 나타낸 것입니다.
이렇게 각각의 패스에서 비교, 교환을 하다가 어떤 시점 이후에 교환이 수행되지 않는다면 그보다 앞쪽의 요소는이미 정렬을 마친 상태입니다. 따라서 두 번째 패스는 첫 요소를 제외한 6개의 요소가 아니라 4개의 요소에 대해서 비교, 교환을 수행하면 됩니다.
앞의 내용을 바탕으로 개선한 코드입니다.
package chap06;
import java.util.Scanner;
// 버블 정렬(버전 3)
class BubbleSort3 {
// 배열 요소 a[idx1]과 a[idx2]의 값을 바꿉니다.
static void swap(int[] a, int idx1, int idx2) {
int t = a[idx1]; a[idx1] = a[idx2]; a[idx2] = t;
}
// 버블 정렬(버전 3)
static void bubbleSort(int[] a, int n) {
int k = 0; // a[k]보다 앞쪽은 정렬을 마친 상태
while (k < n - 1) {
int last = n - 1; // 마지막으로 요소를 교환한 위치
for (int j = n - 1; j > k; j--)
if (a[j - 1] > a[j]) {
swap(a, j - 1, j);
last = j;
}
k = last;
}
}
public static void main(String[] args) {
Scanner stdIn = new Scanner(System.in);
System.out.println("버블 정렬(버전 3)");
System.out.print("요솟수：");
int nx = stdIn.nextInt();
int[] x = new int[nx];
for (int i = 0; i < nx; i++) {
System.out.print("x[" + i + "]：");
x[i] = stdIn.nextInt();
}
bubbleSort(x, nx); // 배열 x를 단순교환정렬
System.out.println("오름차순으로 정렬했습니다.");
for (int i = 0; i < nx; i++)
System.out.println("x[" + i + "]＝" + x[i]);
}
}
정렬 알고리즘 시간복잡도 비교
- 단순(구현 간단) 하지만 비효율적인 방법
- 삽입 정렬, 선택 정렬, 버블 정렬
- 복잡하지만 효율적인 방법
- 퀵 정렬, 힙 정렬, 합병 정렬, 기수 정렬
참고
자료구조와 C(도서)
Do It 자료구조와 함께 배우는 알고리즘 입문(자바 편)
gmlwjd9405.github.io/2018/05/06/algorithm-bubble-sort.html
'컴퓨터 공학 > 자료구조' 카테고리의 다른 글
| 정렬2 (단순 삽입 정렬, 병합 정렬) (0) | 2020.10.29 |
|---|---|
| 그래프 (0) | 2020.10.21 |
| 트리(Tree) (0) | 2020.10.17 |
| 스택(Stack) , 큐(Queue) (0) | 2020.10.15 |
| 선형검색 , 이진 검색 , 해시법 (0) | 2020.10.13 |
