찰떡개발자 코딩

여러가지 정렬 알고리즘 중 선택정렬, 버블정렬, 삽입정렬에 대해 정리를 해보려고 한다.

1). 삽입정렬 (Insortion Sorting) :

삽입정렬은 기준이 되는 인덱스의 앞쪽을 검사하여 기준이 되는 인덱스가 들어갈 자리를 찾아서 삽입하는 정렬이다.

class Sort {
	public List<Integer> sortNum(int[] arrs) {
		List<Integer> list = new LinkedList<Integer>();
		loop:for (Integer num : arrs) {
			for (int i = 0; i < list.size(); i++) {
				if(list.get(i)>num) {
					list.add(i,num);
					continue loop;
				}
			}
			list.add(num);
		}
		return list;
	}
}

public class TEST {

    public static void main(String[] args) throws IOException {
    	int[] numbers = {9,2,3,5,1,6,8};
    	Sort s = new Sort();
		for(Integer num: s.sortNum(numbers))
			System.out.print(num +" ");
    }
}

2021/03/03 업데이트 => 더 간단한 코드로 수정

배열만 사용했던 코드를 LinkedList의 장점인 삽입삭제가 용이한 점을 사용하여 코드 수정

정렬된 배열이라면 새 리스트의 끝까지 반복문을 실행해야하므로 O(N2)이라는 시간이 걸리게되고,

역순으로 정렬된 리스트를 정렬한다면 새 리스트에 그대로 넣게 되므로 O(N)이라는 성능을 가진다.

기존코드 :

public static void main(String[] args) {
		//삽입정렬 테스트
        System.out.println();
        System.out.println("=======삽입정렬=======");
        int c[] = {68, 9, 32, 2, 14, 7, 31, 26};
        System.out.printf("\n정렬할 원소 :");
        for(int v : c) {
            System.out.printf("%3d ", v);
        }
        System.out.println();
        s.insertSort(c);
}
 class Sort {
 
    public void insertSort(int a[]) {
        int size = a.length;
        for(int i=1; i<size; i++) {
            int key = a[i];
            int j = 0;
            for(j=i-1; j>=0;j--){ // i-1 ~ 0
                if(a[j]>key){
                    a[j+1] = a[j];
                }else{
                    break;
                }
            }
            a[j+1] = key;
            System.out.printf("\n삽입정렬 %d 단계 : ",i);
            for(int v : a) {
                System.out.printf("%3d ", v);
            }
        }
        System.out.println();
    }

2). 버블정렬(Bubble Sorting) : 

배열의 시작점에서부터 인접하는 두 항목의 값을 비교하여 올바른 순서(오름차순 또는 내림차순)로 되어있지 않으면 서로 위치를 교환하는 정렬방법이다.

public static void main(String[] args) {
		//버블정렬 테스트
        System.out.println();
        System.out.println("=======버블정렬=======");
        int b[] = {68, 9, 32, 2, 14, 7, 31, 26};
        System.out.printf("\n정렬할 원소 :");
        for(int v : b) {
            System.out.printf("%3d ", v);
        }
        System.out.println();
        s.bubbleSort(b);
}
 class Sort {
 
     public void bubbleSort(int a[]) {
        int size = a.length;
        for(int i=size-1; i>0; i--) {
            System.out.printf("\n버블 정렬 %d 단계 : ", size-i);
            for(int j=0; j<i; j++) {
                if(a[j] > a[j+1]) {
                    int temp = a[j];
                    a[j] = a[j+1];
                    a[j+1] = temp;
                }
                System.out.printf("\n\t");
                for(int v : a) {
                    System.out.printf("%3d ", v);
                }
            }
        }
        System.out.println();
    }
}

3). 선택정렬(Selection Sorting) :

전체 원소들 중에서 기준 위치에 맞는 원소를 선택하여 자리를 교환하는 방식으로 정렬

1. 전체 원소 중에서 가장 작은 원소를 찾아서 선택하여 첫 번째 원소와 자리를 교환

2. 그 다음 두 번째로 작은 원소를 찾아 선택하여 두 번째 원소와 자리를 교환

3. ... 반복

public static void main(String[] args) {
		//선택정렬 테스트
        System.out.println("=======선택정렬=======");
        int a[] = {68, 9, 32, 2, 14, 7, 31, 26};
        Sort s = new Sort();
        System.out.printf("\n정렬할 원소 :");
        for(int v : a) {
            System.out.printf("%3d ", v);
        }
        System.out.println();
        s.selectionSort(a);
}
 class Sort {
        public void selectionSort(int a[]) {
        	for(int i=0; i<a.length-1; i++) {
           	 	int min = i;
          	  	for(int j=i+1; j<a.length; j++) {
                	if(a[j] < a[min]) { //오름차순
                    	min = j;
                	}
            	}
            int temp = a[min];
            a[min] = a[i];
            a[i] = temp;
            System.out.printf("\n선택 정렬 %d 단계 : ", i+1);
            for(int v : a) {
                System.out.printf("%3d ", v);
            }
        }
        System.out.println();
    }
}