정렬 알고리즘 - 선택정렬, 삽입정렬, 거품정렬

선택정렬 - 시간복잡도O(n^2)

단계마다 가장 작은 수를 찾아서 왼쪽에 배치하며 정렬하는 방법이다.

즉, 5개의 요소가 있다면 5개중에 가장 작은 수를 찾아 제일 왼쪽에 배치하고, 나머지 4개중에 가장 작은수, 3개중에 가장 작은 수 순으로 왼쪽으로 배치해 나가는 것이다.

public static void sort(int[]arr) {
		int min;		// 최솟값 인덱스
		for(int i=0; i<arr.length;i++) {
			min = i;	// 제일 왼쪽의 수부터 비교 
			for(int j = i+1;j<arr.length;j++) {
				if(arr[min]>arr[j]) {
					min=j;	// 작은 값이 나오면 그 값의 인덱스를 min에 넣음
				}
			}
			swap(arr, i, min);	// 단계의 가장 작은수를 제일 왼쪽으로 배치 
		}		
	}
	
	public static void swap(int[] arr, int i, int j) { // 자리를 바꾸는 메서드
		int temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}

 

삽입정렬 - 시간복잡도O(n^2)

모든요소를 앞에서부터 차례대로 이미 정렬된 부분과 비교하여, 적절한 위치에 삽입해 가며 정렬하는 방식

public static void sort(int[]arr) {
		for(int i=1; i<arr.length;i++) {
			int j = i;	
			for(int k=i-1;k>=0;k--) {
				if(arr[j]<arr[k]) {
					swap(arr,j,k);
					j=k;	// 위치를 바꾼후 인덱스 값을 바꾼 위치의 인덱스 값으로 설정
				}
			}
		}
	}
	
	public static void swap(int[] arr, int i, int j) { // 자리를 바꾸는 메서드
		int temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}

2번째 요소부터 시작하며, 이전의 요소와 비교하며 정렬한다.

3번째 요소부터는 위치를 바꾸게 되면 비교하려는 수의 인덱스가 바뀌므로 인덱스 값을 바꾸는 코드가 필요하다.

 

거품정렬 - 시간복잡도O(n^2)

인접한 두 원소를 검사하여 정렬하는 방식

 

import java.util.Scanner;

public class Main {	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int M = sc.nextInt();
		int[] arr = new int[M];
		for(int i=0;i<arr.length;i++) {
			arr[i] = sc.nextInt();
		}		
		sort(arr);
		for(int i=0;i<arr.length;i++) {
			System.out.println(arr[i]);
		}
		
	}
	
	public static void sort(int[]arr) {
		
		for(int j = arr.length-1;j>=1;j--) {
			for(int i=0; i<j;i++) {			
					if(arr[i+1]<arr[i]) {
						swap(arr,i+1,i);	
					}
			}
		}
	}
	
	public static void swap(int[] arr, int i, int j) { // 자리를 바꾸는 메서드
		int temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}
}

 - 이중 for문으로 인접한 두 원소를 비교하여 가장 큰 수부터 오른쪽에 정렬시켜 나간다.