[Java] sort(정렬)

 

정렬이란 이름 , 학번 , 키 등 핵심 항목의 대소 관계에 따라 데이터 집합을 일정한 순서로 나열하는 작업을 말한다. 정렬 알고리즘을 이용해 데이터를 정렬하면 검색을 더 쉽게 할 수 있다. 값이 작은 데이터를 앞 쪽에 놓으면 오름차순 정렬, 반대로 놓으면 내림차순 정렬이라고 한다.

 

정렬 알고리즘의 핵심 요소는 교환,선택,삽입이다. 대부분의 정렬 알고리즘은 이 3가지 요소를 응용한 것이다. 

 

1. 버블 정렬

버블 정렬은 이웃한 두 요소의 대소 관계를 비교하고 필요에 따라 교환을 반복하는 알고리즘으로 단순 교환 정렬이라고도 한다.

 

먼저 자료 7을 4와 교환하고 다음에 7과 5을 교환하고 7과 1을 교환하고 7과 4을 교환한다. 첫번째 과정을 수행하면 가장 큰 원소가 끝에 배치되게 된다.

두번째로 4와 5를 비교하지만 교환하지 않고 5와 1을 교환하고 5와 3을 교환한다. 두번째 과정을 수행하면 두번째로 큰 원소가 가장 큰 원소 뒤에 배치되게 된다.

세번째로 4와 1을 교환하고 4 3을 교환한다. 

마지막으로 1과 3을 비교하지만 교환하지 않는다. 이로써 버블 정렬이 수행이 완료 되었다.

public class BubbleSort {
	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=n-1 ; i >= 0 ; i--)
			for(int j=0 ; j < i ; j++) 
				if(a[j] < a[j+1])		// 부등호의 방향으로 오름차순, 내림차순 변환가능
					swap(a,j,j+1);
	}
	public static void main(String[] args) {
		  int n = 5;
		  int list[] = {7,4,5,1,3};
		  
		  bubbleSort(list,5);
		  
		  for(int i = 0; i < list.length ; i++) {
			  System.out.println("list["+i+"] = "+ list[i]);
		  }


	}
}

버블 정렬을 최적화 하는 코드는 원소를 교환 할 때마다 교환 횟수를 기록하여 교환 횟수가 0 이면 반복문을 

탈출하는 방식으로 개선 해 볼 수 있다.

static void bubbleSort(int[] a, int n ) {
		for(int i = n-1 ; i >= 0 ; i--) {
			int exchange = 0;
			for(int j = 0; i > j ; j++) {
				if(a[j] < a[j+1]) {
					swap(a,j,j+1);
					exchange++;
					
				}
				if(exchange == 0 ){
					break;
				}
			}
		}
	}

2. 선택 정렬

단순 선택 정렬은 가장 작은 요소를 맨 앞으로 이동하고, 두 번째 작은 요소는 맨 앞에서 두 번째로 이동하는 등의 작업을 반복하는 알고리즘이다. 

선택 정렬은 최소값을 탐색하여 최소값을 가장 왼쪽에 있는 정렬 되지 않은 원소와 교환하는 방식으로 진행 된다. 

첫 번째 자료 9를 두 번째 자료부터 마지막 자료까지와 비교하여 가장 작은 값을 첫 번째 위치에 옮겨 놓는다. 다음 두번째

자료 6을 세번쨰 자료부터 마지막 자료까지 비교하여 가장 작은 값을 두 번쨰 위치에 옮겨 놓는다. 세 번째 자료 7을 네 번째 자료부터 마지막 자료까지와 비교하여 가장 작은 값을 세 번째 위치에 옮겨놓는다. 네 번째 자료 9와 마지막에 있는 7을 

비교하여 서로 교환한다.

public class selectionSort {
	static void swap(int[] a, int idx1, int idx2) {
		int temp = idx1;
		idx1 = idx2;
		idx2 = temp;
	}
	
	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) {
		int list[] = {9,6,7,3,5};
		
		selectionSort(list,5);
		
		for(int i = 0; i < list.length ; i++) {
			System.out.println("list["+i+"] = " + list[i]);
		}
	}

}

3. 삽입 정렬

삽입 정렬은 선택한 요소를 그보다 더 앞쪽의 알맞는 위치에 삽입하는 작업을 반복하여 정렬하는 알고리즘이다. 

 

 

선택 정렬을 구현할 때 중요한 점은 j 변수를 for문 안쪽에 선언하는 것이 아니라 따로 선언해 주어야 한다는 것이다.

public class insertionSort {
	static void insertionSort(int[] a,int n) {
		for(int i = 1; i < n ; i++) {
			int j;
			int temp = a[i];
			for(j = i ; j > 0 && a[j-1] > temp; j--) {
				a[j] = a[j-1];
			}
			a[j] = temp;
		}
	}
	public static void main(String[] args) {
		int list[] = {8, 5, 6, 2, 4};
		
		insertionSort(list, 5);
		
		for(int i = 0; i < list.length; i++) {
			System.out.println("list["+i+"] = " + list[i]);
		}

	}

}

 

4. 합병 정렬

병합 정렬은 벼열을 앞부분과 뒷부분 둘로 나누어 각각 정렬한 다음 병합하는 작업을 반복하여 정렬하는 알고리즘이다.

일반적인 방법으로 구현했을 떄 이 정렬은 안정 정렬에 속하며, 분할 정복 알고리즘의 하나이다. 병합정렬의 시간복잡도는 O(n)이다. 병합 정렬 알고리즘의 순서를 정리하면 다음과 같다.

1)  배열이 앞부분을 병합 정렬로 정렬한다.
2)  배열의 뒷부분을 병합 정렬로 정렬한다.
3)  배열의 앞부분과 뒷부분을 병합한다.

 

package ch06_sort;

import java.util.Scanner;

public class MergeSort {
	static int sorted[] = new int[8];
	static void merge(int list[], int left, int mid, int right) {
		int i,j,k,l;
		i = left;
		j = mid + 1 ;
		k = left;
		
		while(i <= mid && j <= right)
			if(list[i] <= list[j])
				sorted[k++] = list[i++];
			else 
				sorted[k++] = list[j++];
		if(i > mid) {
			for(l = j ; l <= right ; l++)
				sorted[k++] = list[l];
		}
		
		else {
			for(l = i; l <= mid ; l++)
				sorted[k++] = list[l];
		}
		
		for(l = left; l <= right ; l++) {
			list[l] = sorted[l];
		}
	}
	
	static void merge_sort(int list[], int left, int right) {
		int mid;
		
		if(left < right) {
			mid = (left + right) / 2;
			merge_sort(list,left,mid);
			merge_sort(list,mid+1,right);
			merge(list,left,mid,right);
		}
	}
	
	
	public static void main(String[] args) {
		int i;
		int[] list = {21,10,12,20,25,13,15,22};
		
		merge_sort(list, 0, list.length-1);
		
		for(i = 0; i < list.length -1 ; i++) {
			System.out.print(list[i]+ " ");
		}

	}

}

 

https://gmlwjd9405.github.io/2018/05/06/algorithm-bubble-sort.html

[알고리즘] 버블 정렬(bubble sort)이란 - Heee's Development Blog