정렬 알고리즘 - 삽입 정렬, 선택 정렬, 버블 정렬

1. 삽입 정렬 (Insert Sort)

 

2번째 원소부터 앞쪽의 원소들과 비교하면서 재자리를 찾아가는 방법

for(index 1 부터 전체 배열 순회) {
  insert_obj = arr[i];

  for(i-1 번째 원소부터 왼쪽으로 순회) {

    //만약 현재 원소가 삽입할 원소보다 크다면
    if(arr[j] > insert_obj) {
      //오른쪽으로 한칸 땡기면서 자리를 마련한다
      arr[j+1] = arr[j];
    }
    else {
       break;
    }
  }
  
  //마련한 자리에 삽입
  arr[j+1] = insert_obj;
}

 

2. 선택 정렬 (Selection Sort)

 

1번째 원소부터 최솟값을 찾아 자리 교환을 해나가는 방법

for(원소 전체 순회) {
  //최소값을 가진 인덱스 유지
  min_index = i;
  
  for(i+1 부터 원소 전체 순회) {
    if(최소값 보다 현재 원소가 더 작다면) {
      //최소 인덱스 교체
      min_index = j;
    }
  }

  //순회가 끝난 후 현재 원소와 최소 값을 교환
  temp = arr[i];
  arr[i] = arr[min_index];
  arr[min_index] = temp;
}

 

 

3. 버블 정렬 (Bubble Sort)

 

바로 옆의 원소와 비교하면서 순서가 맞지 않을 경우 교환하는 방법

for(전체 원소 순회) {
  for(1번째 원소부터 마지막에서 1개 전 원소까지 순회) {
    if(n번째와 n+1번째의 순서가 맞지 않을 경우) {
      //원소 교환
      temp = arr[j];
      arr[j] = arr[i];
      arr[i] = temp;
    }
  }
}

 

 

3. 소스 코드

package sort;

import java.util.Arrays;
import java.util.Random;

public class SortTest {

	//배열 설정 값
	private static int MAX_LEN = 12;
	private static int MAX_INT = 30;

	public static void main(String[] args) {

		SortTest me = new SortTest();

		int arr[] = me.getRandomNumberArr();

		System.out.println("정렬 전 >> " + Arrays.toString(arr));

		//1. 삽입 정렬
		int insertSortarr[] = me.InsertionSort(arr);
		System.out.println("삽입 정렬 >> " + Arrays.toString(insertSortarr));

		//2. 선택 정렬
		int selectionSortarr[] = me.InsertionSort(arr);
		System.out.println("선택 정렬 >> " + Arrays.toString(selectionSortarr));

		//2. 버블 정렬
		int bubbleSortarr[] = me.bubbleSort(arr);
		System.out.println("버블 정렬 >> " + Arrays.toString(bubbleSortarr));

	}

	/**
	 * 삽입 정렬 알고리즘
	 * @param arr
	 * @return
	 */
	int[] InsertionSort(int[] arrParam) {
		int i, j;
		int insert_obj;

		int arr[] = arrParam.clone();

		for(i=1; i<MAX_LEN; i++) {
			insert_obj = arr[i];

			for(j=i-1; j>-1; j--) {
				if(arr[j] > insert_obj) {
					//자리 마련하기
					arr[j+1] = arr[j];
				}
				else {
					break;
				}
			}
		arr[j+1] = insert_obj;
		}

		return arr;
	}

	/**
	 * 선택 정렬 알고리즘
	 * @param arr
	 * @return
	 */
	int[] selectSort(int[] arrParam) {
		int i, j;
		int min_index;
		int temp;

		int arr[] = arrParam.clone();

		for(i=0; i<MAX_LEN; i++) {
			min_index = i;
			for(j=i+1; j<MAX_LEN; j++) {
				if(arr[min_index] > arr[j]) {
					min_index = j;
				}
			}

			if(i != min_index) {
				//값 교환
				temp = arr[i];
				arr[i] = arr[min_index];
				arr[min_index] = temp;
			}

		}


		return arr;
	}

	/**
	 * 버블 정렬
	 * @param arr
	 * @return
	 */
	int[] bubbleSort(int[] arrParam) {
		int i, j;
		int temp;

		int arr[] = arrParam.clone();

		for(i=0; i<MAX_LEN; i++) {
			for(j=0; j<MAX_LEN-1; j++) {
				if(arr[i] < arr[j]) {
					temp = arr[j];
					arr[j] = arr[i];
					arr[i] = temp;
				}
			}
		}

		return arr;
	}

	/**
	 * n개의 중복 되지 않는 랜덤 배열 생성
	 * @param len
	 * @param maxNumber
	 * @return
	 */
	int[] getRandomNumberArr() {
		return getRandomNumberArr(MAX_LEN, MAX_INT);
	}

	int[] getRandomNumberArr(int len, int maxNumber) {

		long seed = System.currentTimeMillis();
		Random rand = new Random(seed);

		int arr[] = new int[len];
		int tempInt;
		boolean validIntInserted;

		if(len > maxNumber) {
			System.out.println("랜덤 배열을 만들 수 없음(배열 길이보다 최대 숫자가 큼)");
			return arr;
		}

		//랜덤 배열 생성
		for(int i=0; i<len; i++) {

			while(true) {
				validIntInserted = true;
				tempInt = rand.nextInt(maxNumber);
				for(int j=0; j<i; j++) {
					if(arr[j] == tempInt) {
						validIntInserted = false;
					}
				}
				if(validIntInserted) {
					arr[i] = tempInt;
					break;
				}
			}

		}

		return arr;

	}


}

 

결과

정렬 전 >> [28, 17, 1, 14, 8, 25, 4, 10, 12, 19, 13, 15]
삽입 정렬 >> [1, 4, 8, 10, 12, 13, 14, 15, 17, 19, 25, 28]
선택 정렬 >> [1, 4, 8, 10, 12, 13, 14, 15, 17, 19, 25, 28]
버블 정렬 >> [1, 4, 8, 10, 12, 13, 14, 15, 17, 19, 25, 28]