[알고리즘] 선택 정렬 코드 및 불안정 정렬 확인

package class02;

public class Test01 {

	public static void main(String[] args) {

		/*
		 * 선택정렬 코드 작성
		 * */

		int[] datas = {1, 50, 34, 7};
		int tmp, minIdx;
		
		for (int a = 0; a < datas.length - 1; a++) {
			minIdx = a;
			for (int i = a + 1; i < datas.length; i++) {
				if (datas[i] < datas[minIdx]) {
					minIdx = i;
				}
			}
			tmp = datas[a];
			datas[a] = datas[minIdx];
			datas[minIdx] = tmp;
		}
		
		System.out.print("[ ");
		for (int data: datas) {
			System.out.print(data + " ");
		}
		System.out.println("]");
	}
	
	/*
	 * 디버깅표
	 * 
	 * datas               minIdx    a    a < 3    i    i < 4    datas[i] < datas[minIdx]
	 * ==================================================================================
	 * [ 1, 50, 34, 7 ]              0    T
	 *                     0                       1    T        F
	 *                                             2    T        F
	 *                                             3    T        F
	 *                                             4    F
	 * [ 1, 50, 34, 7 ]              1    T
	 *                     1                       2    T        T
	 *                     2                       3    T        T
	 *                     3                       4    F
	 * [ 1, 7, 34, 50 ]              2    T
	 *                     2                       3    T        F
	 *                                             4    F
	 * [ 1, 7, 34, 50 ]              3    F       
	 * 
	 * */

}

 

선택 정렬을 공부하다가 추가 의문 사항이 생겼다

선택 정렬은 불안정 정렬이다..왠지 안정일 거 같은 느낌이 들어서 확인해보자

 

 

package class02;

import java.util.Scanner;

class Pair {
    private int n;
    private char c;

    Pair(int n, char c) {
        this.n = n;
        this.c = c;
    }
//    Pair() {
//    }

    public int getN(){
        return n;
    }

    public char getC(){
        return c;
    }
}


public class Test02 {

	public static void main(String[] args) {

		/*
		 * 선택정렬 코드 작성
		 */

		/*
		 * 
		 * 여러 테스트 케이스를 넣기 위한 콘솔 입력 받기 입력 예시는 아래와 같다 3 5 --> 테스트 케이스의 수, 각 케이스의 길이 0 1 5
		 * 2 6 --> 각 테스트 케이스 2 2 3 4 5 4 2 12 9 0
		 * 
		 */

		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int len = sc.nextInt();

		for (int i = 0; i < n; i++) {
			
			/*
			 * 동일 값을 구분하기 위해 pair의 배열로 저장하자
			 * pair의 규칙은 다음과 같다
			 * <값, 구분자>
			 * <1, a>, <1, b> --> 같은 1의 값이지만 a와 b로 구분할 수 있다
			 * */
//			Pair p = new Pair(1, 'c');
			Pair[] datas = new Pair[len];
			char c = 'a';
			for (int j = 0; j < len; j++) {
				datas[j] = new Pair(sc.nextInt(), c++);
			}

			// 정렬 전 확인
			System.out.print("[ ");
			for (Pair data : datas) {
				System.out.print("<" + data.getN() + "," + data.getC() + "> ");
			}
			System.out.println("]");

			// 정렬
			int minIdx;
			Pair tmp;
			
			for (int a = 0; a < datas.length - 1; a++) {
				minIdx = a;
				for (int k = a + 1; k < datas.length; k++) {
					if (datas[k].getN() < datas[minIdx].getN()) {
						minIdx = k;
					}
				}
				tmp = datas[a];
				datas[a] = datas[minIdx];
				datas[minIdx] = tmp;
			}

			// 결과 확인 
			System.out.print("[ ");
			for (Pair data : datas) {
				System.out.print("<" + data.getN() + "," + data.getC() + "> ");
			}
			System.out.println("]");
		}
	}
}

 

코드는 위와 같이 작성했다

Pair를 이용해서 같은 값을 구분했다

불안정되는 케이스는 바로 찾았다

중복되는 3의 값이 0, 1이 정렬되는 과정에서 뒤섞이게 된다

 

궁금증 해결!