[JAVA] 정렬(Sort) - 버블 정렬, 선택정렬, 삽입정렬

정렬이란 이름, 학번, 키 등 핵심 항목(key)의 대소 관계에 따라 데이터 집합을 일정한 순서로 줄지어 늘어서도록 바꾸는 작업을 말합니다.

키 값이 작은 데이터를 앞쪽에 놓으면 오름차순 정렬, 반대로 놓으면 내림차순 정렬이라 합니다.

정렬 알고리즘의 핵심 요소는 교환, 선택, 삽입입니다.

---

버블 정렬(bubble sort)

버블 정렬은 이웃한 두 요소의 대소 관계를 비교하여 교환을 반복합니다.

 

1. 앞에서부터 현재 원소와 바로 다음의 원소를 비교합니다.

2. 현재 원소가 다음 원소보다 크면 원소를 교환합니다.

3. 다음 원소로 이동하여 해당 원소와 그 다음원소를 비교합니다.

 

즉, 그림으로 보면 다음과 같은 과정을 거칩니다.

총 라운드는 배열 크기 - 1 번 진행되고,

각 라운드별 비교 횟수는 배열 크기 - 라운드 횟수 만큼 비교합니다.

 

 

▶ 버블 정렬 구현하기

import java.util.Scanner;

public class BubbleSort2 {
	
	public static void swap(int[] arr, int idx1,int idx2) {
		int temp = arr[idx1];
		arr[idx1] = arr[idx2];
		arr[idx2] = temp;
	}

	public static void bubbleSort(int[] arr, int n) {
		for (int i = 0; i < n-1; i++) {
			int change=0; ///교환횟수
			for (int j = 0; j < n-1-i; j++) {
				if(arr[j]>arr[j+1]) {
					swap(arr,j,j+1);
					change++;
				}
			}
			if(change==0) {break;}
		}
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		System.out.print("요솟 수 :");
		int n = sc.nextInt();
		int[] arr = new int[n];

		for (int i = 0; i < arr.length; i++) {
			System.out.print("arr[" + i + "] : ");
			arr[i] = sc.nextInt();
		}

		bubbleSort(arr, n);

		System.out.println("오름차순으로 정렬 했습니다.");
		for (int i = 0; i < arr.length; i++) {
			System.out.print("arr[" + i + "] : " + arr[i]);
			System.out.println();
		}

	}
}

위에 코드에서 change변수를 두고 change가 0이될 때 종료시키는 코드를 쓴것은,

어떤 라운드에서 요소의 교환 횟수가 0 이면 더이상 정렬할 요소가 없다는 뜻으로 정렬작업을 멈춘다는 뜻입니다.

이런 방식을 도입하면 짧은 시간에 정렬을 마칠 수 있습니다.

 

 

선택정렬(selection sort)

선택 정렬은 가장 작은 요소부터 선택해 알맞은 위치로 옮겨서 순서대로 정렬하는 알고리즘 입니다.

 

1. 주어진 리스트에서 최솟값을 찾습니다.

2. 최솟값을 맨 앞 자리의 값과 교환합니다.

3. 맨 앞 자리를 제외한 나머지 값들 중 최솟값을 찾아 위와 같은 방법으로 반복합니다. 

 

 

즉, 그림으로 보면 다음과 같은 과정을 거칩니다.

 

▶ 선택 정렬 구현하기

import java.util.Scanner;

public class SelectionSort {
	
	public static void swap(int[]arr, int idx1, int idx2) {
		int temp = arr[idx1];
		arr[idx1]=arr[idx2];
		arr[idx2]=temp;
	}

	public static void selectionSort(int[] arr, int n) {
		for (int i = 0; i < n - 1; i++) {
			int min = i;
			for (int j = i + 1; j < n; j++) {
				if (arr[j] < arr[min]) {
					min = j;
				}
			}
			swap(arr, i, min );
		}
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		System.out.print("요솟 수 :");
		int n = sc.nextInt();
		int[] arr = new int[n];

		for (int i = 0; i < arr.length; i++) {
			System.out.print("arr[" + i + "] : ");
			arr[i] = sc.nextInt();
		}

		selectionSort(arr, n);

		System.out.println("오름차순으로 정렬 했습니다.");
		for (int i = 0; i < arr.length; i++) {
			System.out.println("arr[" + i + "] : " + arr[i]);
		}
	}
}

1. 아직 정렬하지 않은 부분에서 가장 작은 키의 값(arr[min])을 선택합니다.

2. arr[min]과 아직 정렬하지 않은 부분의 첫 번째 요소를 교환합니다.

 

 

삽입 정렬(Insertion sort)

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

 

1. 현재 타겟이 되는 숫자와 이전 위치에 있는 원소들을 비교합니다. (첫 번째 타겟은 두 번째 원소부터 시작합니다.)

2. 타겟이 되는 숫자가 이전 위치에 있던 원소보다 작다면 위치를 서로 교환합니다.

3. 그 다음 타겟을 찾아 위와 같은 방법으로 반복합니다. 

 

 

즉, 그림으로 보면 다음과 같은 과정을 거칩니다.

 

▶ 삽입 정렬 구현하기

public class InsertionSort {

	public static void insertionSort(int[] a, int size) {
		public static void insertionSort(int[] a, int size) {
		for (int i = 0; i < a.length; i++) {
			for (int j = i+1; j > 0; j--) {
				if(j==a.length) {break;}
				if(a[j]<a[j-1]) {
					int temp = a[j];
					a[j]=a[j-1];
					a[j-1]=temp;
				}else {break;}
			}
		}
	}

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		System.out.print("요솟 수 :");
		int n = sc.nextInt();
		int[] arr = new int[n];

		for (int i = 0; i < arr.length; i++) {
			System.out.print("arr[" + i + "] : ");
			arr[i] = sc.nextInt();
		}

		insertionSort(arr, n);

		System.out.println("오름차순으로 정렬 했습니다.");
		for (int i = 0; i < arr.length; i++) {
			System.out.println("arr[" + i + "] : " + arr[i]);
		}

	}
}

 

---

이상으로 버블정렬과 선택정렬, 삽입정렬에 대해 알아보았습니다.