[정렬] 버블정렬,선택정렬,삽입정렬, 셸 정렬

1. 알고리즘이란?

https://why-dev.tistory.com/6?category=917883 

[컴퓨터 공학_복습] 알고리즘 정의, 검색과 정렬 알고리즘

 

2. 정렬

- 정의 : 이름,학번,키 등 핵심항목(key)의 대소관계에 따라 순서대로 값을 나열하는 것

- 안정성 : 키값이 같은 요소의 순서가 정렬 후에도 유지되는 것

   (ex. 같은 점수를 지닌 두 학생에 대해 학번으로 순번을 지정)

- 내부 정렬과 외부 정렬 : 정렬할 모든 데이터를 하나의 배열에 저장할 수 있을 때에 내부 정렬을 사용한다. 

- 정렬의 속도 비교 : 

https://youtu.be/ZZuD6iUe3Pc

 

3. 버블정렬, 선택정렬, 삽입정렬

- Big O는 셋 다 n^2이지만, 속도는 다르다.   - (정렬이 안 된 자료들을 정렬할때) 버블정렬 보다는 선택정렬이 교환횟수가 적어서 상대적으로 더 빠르다.    - (이미 정렬이 어느 정도 된 경우) 삽입정렬을 쓰는 것이 좋다

 

1) 버블정렬 

원리 ) 안쪽에서 두개의 값을 비교한다 
       --> 한 줄 비교가 다 끝나면 마지막 값이 가장 큰 값(또는 가장 작은 값)
       --> 안 쪽은 n-1-i 만큼 두개씩 비교 & swap하면 된다.
       바깥쪽에서 이 과정을 n-1만큼 반복한다.

[코드]

package _02_정렬;

import java.util.Arrays;

public class _04_BubbleSort {

	public static void main(String[] args) {
		
		int[] arr = new int[10];
		
		random(arr);
		
		System.out.println(Arrays.toString(arr));
		
		//오름차순 버블 정렬을 구현하라
		int tmp;
		for (int i = 0; i < arr.length-1; i++) {
			for (int j = 0; j < arr.length-1-i; j++) {
				if (arr[j] > arr[j+1]) {
					tmp = arr[j];
					arr[j] = arr[j+1];
					arr[j+1] = tmp;
				}
			}
		}
		System.out.println(Arrays.toString(arr));
		
		//내림차순 버블 정렬을 구현하라
		for (int i = 0; i < arr.length-1; i++) {
			for (int j = 0; j < arr.length-1-i; j++) {
				if (arr[j] < arr[j+1]) {
					tmp = arr[j];
					arr[j] = arr[j+1];
					arr[j+1] = tmp;
				}
			}
		}
		System.out.println(Arrays.toString(arr));

	}
	
	public static int[] random(int[] arr) {
		
		OUTER :
		for (int i = 0; i < arr.length; i++) {
			
			arr[i] = (int)(Math.random()*10)+1;
			
			for (int j = 0; j < i; j++) {
				
				if (arr[j] == arr[i]) {
					i--;
					continue OUTER;
				}
			}
		}
		
		return arr;
		
	}

}

>> 결과

[10, 3, 8, 9, 4, 1, 7, 5, 2, 6]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
[10, 9, 8, 7, 6, 5, 4, 3, 2, 1]

 

2) 선택정렬 

원리 ) i index를 min(or max)으로 지정하고, 나머지 값들을 하나씩 비교한 뒤, 교환한다.

[코드]

package _02_정렬;

import java.util.Arrays;

public class _05_SelectionSort {

	public static void main(String[] args) {

		int[] arr = new int[10];
		
		random(arr);
		
		System.out.println(Arrays.toString(arr));
		
		//오름차순 선택정렬을 구현하라
		int min, tmp;
		for (int i = 0; i < arr.length-1; i++) {
			min = i; // 하나의 요소를 min으로 선택(이 값보다 작은 값을 찾는다)
			for (int j = i+1; j < arr.length; j++) {
				if (arr[j] < arr[min]) {
					min = j;
				}
			}
			//i위치값과 min값을 swap
			tmp = arr[i];
			arr[i] = arr[min];
			arr[min] = tmp;
		}
		System.out.println(Arrays.toString(arr));
		
		//내림차순 선택정렬을 구현하라
		int max;
		for (int i = 0; i < arr.length-1; i++) {
			max = i;
			for (int j = i+1; j < arr.length; j++) {
				if (arr[j] > arr[max]) {
					max = j;
				}
			}
			//i위치값과 max값을 swap
			tmp = arr[i];
			arr[i] = arr[max];
			arr[max] = tmp;
		}
		System.out.println(Arrays.toString(arr));

	}
	
	public static int[] random(int[] arr) {
		
		OUTER :
		for (int i = 0; i < arr.length; i++) {
			
			arr[i] = (int)(Math.random()*10)+1;
			
			for (int j = 0; j < i; j++) {
				
				if (arr[j] == arr[i]) {
					i--;
					continue OUTER;
				}
			}
		}
		
		return arr;
		
	}

}

>> 결과

[2, 9, 8, 5, 10, 1, 6, 4, 3, 7]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
[10, 9, 8, 7, 6, 5, 4, 3, 2, 1]

 

3) 삽입 정렬 (Insertion Sort)

- 거의 다 정렬된 상태의 데이터를 다시 정렬할 때, 가장 효과적인 알고리즘 (위 정렬 속도 비교 확인)

- 원리 : 아직 정렬되지 않은 부분의 첫번째 요소를 정렬한 부분의 알맞은 위치에 삽입한다.

- 장점 : 정렬이 되었거나 또는 그 상태에 가까우면 정렬 속도가 아주 빠름

- 단점 : 삽입할 곳이 멀리 떨어지면 이동(대입)하는 횟수가 많다

   (ex. 0~10까지 중 0제외 나머지는 정렬된 상태이나, 0값이 인덱스의 끝에 위치)

[코드]

package _02_정렬;

import java.util.Arrays;

public class _02_InsertionSort {

	public static void main(String[] args) {
		int[] arr = new int[10];
		
		random(arr);
		
		System.out.println(Arrays.toString(arr));
		
		//오름차순 삽입정렬을 구현하라
		int tmp;
		for (int i = 1; i < arr.length; i++) {
			tmp = arr[i];
			int j;
			
			for (j = i; j > 0 && arr[j-1] > tmp; j--) {
				arr[j] = arr[j-1];
			}
			arr[j] = tmp;	
		}
		System.out.println(Arrays.toString(arr));
		
		//내림차순 삽입정렬을 구현하라
		for (int i = 1; i < arr.length; i++) {
			tmp = arr[i];
			int j;
			for (j = i; j > 0 && arr[j-1] < tmp; j--) {
				arr[j] = arr[j-1];
			}
			arr[j] = tmp;
		}
		System.out.println(Arrays.toString(arr));
	}
	
	public static int[] random(int[] arr) {
		
		OUTER :
		for (int i = 0; i < arr.length; i++) {
			
			arr[i] = (int)(Math.random()*10)+1;
			
			for (int j = 0; j < i; j++) {
				
				if (arr[j] == arr[i]) {
					i--;
					continue OUTER;
				}
			}
		}
		
		return arr;
		
	}

}

>> 결과

[3, 1, 6, 4, 10, 2, 5, 7, 9, 8]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
[10, 9, 8, 7, 6, 5, 4, 3, 2, 1]

 

4. 셸 정렬 (Shell Sort)

 

 

[ 출처 ]

- 자바의 정석, 남궁성

- Do it! 자료구조와 함께 배우는 알고리즘 입문 [자바편], bogyoh shibata지음

- 기타 : 유투브