1441, 1442, 1443 - 버블 정렬, 선택 정렬, 삽입 정렬

> 전에 C인가 Python인가 배울 때 정렬 관련해서 여러 알고리즘이 있다고 들었는데... 어떤 방법들이 있는지, 그리고 어떤 상황에서 어떤 방법이 빠른지 궁금했다. 나중에 배우게 될 지는 모르겠지만, 그냥 혼자 문제 풀면서 정리해봤다.

 

 

기초 5-4 데이터 정렬

## 1441
버블 정렬
- 인접한 두 원소 검사, 작은 걸 앞으로. (오름차순)

import java.util.Scanner;

public class CodeUp1441 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int[] a = new int[10001];
		int temp;
		int n = sc.nextInt(); // 개수

		for (int i = 1; i <= n; i++) {
			a[i - 1] = sc.nextInt();
		}

		for (int i = 1; i < n; i++) {
			for (int j = 0; j < n - i; j++) {
				if (a[j] > a[j + 1]) {
					temp = a[j];
					a[j] = a[j + 1];
					a[j + 1] = temp;
				}
			}
		}

		for (int i = 0; i < n; i++)
			System.out.println(a[i]);
	}
}

- n개의 원소라 하자.
- 2개씩 묶으면 n-1쌍, n-1번 실행한다.
- 가장 작은 수가 가장 앞에 온다.
- 가장 앞은 됐으니 나머지는 n-1개, 또 둘 씩 묶으면 n-2회 실행.
- 즉 for를 각각 n-1, n-2, n-3, ... 2, 1 회 실행
- 즉 for가 있는 for를 n-1회 실행
- 즉 가장 작은 for를 1+2+3+...+(n-1) = n(n-2)/2회 실행.

 

## 1442
선택 정렬
- 전체 검사, 가장 작은걸 첫 위치로 옮김. 첫 원소 제외 재검색, 반복. (오름차순)

import java.util.Scanner;

public class CodeUp1442 {
	public static void main(String[] args) {
		int[] a = new int[10001];
		int temp, min;
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();

		// input
		for (int i = 1; i <= n; i++) {
			a[i - 1] = sc.nextInt();
		}

		for (int i = 0; i < n - 1; i++) {
			min = i;
			for (int j = i + 1; j < n ; j++) {
				min = (a[j] < a[min]) ? j : min;
			}
			temp = a[i];
			a[i] = a[min];
			a[min] = temp;
		}

		for (int i = 0; i < n; i++)
			System.out.println(a[i]);

	}
}

- n개의 원소라 하자.
- 첫 원소를 한 손에 들고 나머지 n-1개를 차례로 검사하며 더 작은게 나오면 손에 든 원소는 원위치하고 그 원소를 든다. 그렇게 n-1번 검사 후 마지막 손에 들린 원소를 가장 앞으로 옮긴다.
- 가장 작은 수가 가장 앞에 온다.
- 가장 앞은 됐으니 나머지 n-1개로 같은 실행을 한다. 즉 n-2번 검사를 하고 그 중 가장 작은 원소를 두 번째 자리로 옮긴다.
- 즉 for를 각각 n-1, n-2, n-3, ... 2, 1 회 실행
- 즉 for가 있는 for를 n-1회 실행
- 즉 가장 작은 for를 1+2+3+...+(n-1) = n(n-2)/2회 실행.
- 버블 정렬이랑 횟수는 같네...

 

## 1443
삽입 정렬
- 각 원소를 자기 앞 원소와 비교, 자기가 더 작을 시 앞으로 이동. 자기 자리 찾을 때 까지 이동. 마지막 원소까지 반복. (오름차순)

import java.util.Scanner;

public class CodeUp1443 {
	public static void main(String[] args) {
		int[] a = new int[10001];
		int temp;
		int key;

		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();

		for (int i = 0; i < n; i++) {
			a[i] = sc.nextInt();
		}

		for (int i = 1; i < n; i++) { // 1부터 시작이지만 끝까지 감 n-1회
			key = a[i];
			for (int j = i - 1; j > -1; j--) {
				if (a[j] > key) {
					a[j + 1] = a[j];
					a[j] = key;
				} else {
					break;
				}
			}
		}

		for (int i = 0; i < n; i++) {
			System.out.println(a[i]);
		}
	}
}

- n개의 원소라 하자.
- 첫 원소는 앞이 없으니 그냥 둔다. 즉 두 번째(인덱스1) 원소부터 시작.
- [1]이 앞과 비교, 1회
- [2]이 앞과 비교, 최소 1회 최대 2회
- [3]이 앞과 비교, 최소 1회 최대 3회
- ... 마지막 원소 [n-1] 최소 1회 최대 n-1회
- 이미 정렬돼 있을 경우 (n-1)회만 실행하나, 최대 실행 횟수는 n(n-2)/2회로 같다.
- for를 각각 1, 2, 3, ... n-1회 실행
- for가 있는 for를 n-1회 실행
- 최대 n(n-2)/2회로 같다.

 

 

 

 

 

 

 

 

흠,,

몇 회를 비교하고 정렬하는지 이런 건 별로 차이가 없는 것 같고...

사실 시간이 너무 늦어서 이제 자야겠다 다음에 또 알아보자

 

ㅋㅋ;