버블 정렬, 선택 정렬, 삽입 정렬

제로칼로리 2023. 7. 2. 22:12

2023. 7. 2. 22:12

https://www.udemy.com/course/best-javascript-data-structures/

테스트 값

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.concurrent.ThreadLocalRandom;

public class SortEx01 {
	public static void main(String[] args) {
		ThreadLocalRandom current = ThreadLocalRandom.current();
		Integer[] array = current.ints(0,300).distinct().limit(10).boxed().toArray(Integer[]::new);
		System.out.println(array.getClass().getSimpleName()+"   "+ Arrays.toString(array));
		
		//정렬들 저장용
		List<SortStategy<Integer>> list = new ArrayList<>();
		
		for(SortStategy<Integer> sort : list) 
			System.out.printf("%-20s  %s%n",sort.getClass().getSimpleName(),
					Arrays.toString(sort.sort(array)));
	}
	
	static interface SortStategy<T>{
		T[] sort(T[] arr);
		//자리 바꿈 메서드
		default void swap(Integer[] clone, int i, int j) {
			Integer tmp = clone[i];
			clone[i] = clone[j];
			clone[j] = tmp;
		}
	}
}

버블 정렬

큰 값을 뒤로 보내며, 최대반복 수를 점점 줄여간다.

static class BubbleSort implements SortStategy<Integer>{
    static int cnt = 0;

    public Integer[] sort(Integer[] arr) {
        Integer[] clone = arr.clone();

        for(int i=0;i<clone.length-1;i++) {// n -1 번 수행
            for(int j=1;j<clone.length-i;j++) {
                cnt++;
                if(clone[j]<clone[j-1]) {
                    swap(clone, j-1, j);
                }
            }
            System.out.println(Arrays.toString(clone));
        }
        System.out.print("버블소트 cnt("+cnt+")");
        return clone;
    }
}

Integer[]   [113, 247, 171, 173, 243, 35, 66, 223, 85, 83]
[113, 171, 173, 243, 35, 66, 223, 85, 83, 247]
[113, 171, 173, 35, 66, 223, 85, 83, 243, 247]
[113, 171, 35, 66, 173, 85, 83, 223, 243, 247]
[113, 35, 66, 171, 85, 83, 173, 223, 243, 247]
[35, 66, 113, 85, 83, 171, 173, 223, 243, 247]
[35, 66, 85, 83, 113, 171, 173, 223, 243, 247]
[35, 66, 83, 85, 113, 171, 173, 223, 243, 247]
[35, 66, 83, 85, 113, 171, 173, 223, 243, 247]
[35, 66, 83, 85, 113, 171, 173, 223, 243, 247]
버블소트 cnt(45)BubbleSort            [35, 66, 83, 85, 113, 171, 173, 223, 243, 247]

최대 값이 제일 뒤로 가니, 그에 따라 최대 반복 수를 줄여 정렬한다.

버블 정렬 최적화

static class BubbleSortOp implements SortStategy<Integer>{
    Boolean noSwap = false;
    static int cnt = 0;

    public Integer[] sort(Integer[] arr) {
        Integer[] clone = arr.clone();

        for(int i=0;i<clone.length-1;i++) {// n -1 번 수행용 반복문
            noSwap = true;
            for(int j=1;j<clone.length-i;j++) {//자리바꿈 루프
                cnt++;
                if(clone[j]<clone[j-1]) {
                    noSwap = false; // 자리바꿈이 한 번이라도 수행됐다.
                    swap(clone, j-1, j);
                }
            }
            if(noSwap) break; //자리 바꿈이 수행된적이 없으면 수행용 반복은 의미없음
        }
        System.out.print("버블소트 최적화 cnt("+cnt+")");
        return clone;
    }
}

더 이상 교환된 값이 없으면, 더 이상 정렬한 값이 없는 것으로 반복문을 빠져나온다.

Integer[]   [286, 172, 22, 197, 169, 62, 236, 99, 141, 156]
버블소트 cnt(45)BubbleSort            [22, 62, 99, 141, 156, 169, 172, 197, 236, 286]
버블소트 최적화 cnt(39)BubbleSortOp          [22, 62, 99, 141, 156, 169, 172, 197, 236, 286]

선택 정렬

지정된 위치에 최적에 값을 넣는다.

가장 안 좋은 정렬이다. 어떠한 경우에도 n^2 시간 복잡도를 보인다.

//버블 정렬보다 나은 점은 스왑수 최소화, i루프 마다 단 한번의 스왑만 발생
static class SelectionSort implements SortStategy<Integer>{
    public Integer[] sort(Integer[] arr) {
        Integer[] clone = arr.clone();
        for(int i=0;i<clone.length-1;i++) {
            for(int j=i+1;j<clone.length;j++) {
                if(Integer.compare(clone[i], clone[j])>0) {
                    swap(clone, i, j);
                }
            }
        }
        return clone;
    }
}

삽입 정렬

논리적으로 배열안에 서브 배열을 만들어 점차 정렬해가는 정렬

배열의 요소가 1개면, 자연스럽게 정렬된 상태다. 즉, 배열의 요소가 2개부터 정렬이 가능한 상태로 시작 인덱스는 1로 준다.

배열의 요소가 거의 정렬된 상태일 때 매우 빠른 속도를 보인다.

static class InsertSort implements SortStategy<Integer>{
    //논리적으로 순회 마다 작은 서브배열을 만든다고 가정한다.
    //1부터 시작
    public Integer[] sort(Integer[] arr) {
        Integer[] clone = arr.clone();
        //배열이 단 한개는 이미 정렬된 것이다. (논리적 배열)
        for(int i = 1;i<clone.length;i++) {
            //배열 shift 하는 동안 값 손실 때문이 임시 저장
            Integer newMember = clone[i];
            Integer j = i-1;
            //새로운 멤버 clone[i]
            for(;j>=0 && newMember < clone[j];j--) {
                clone[j+1] = clone[j];
            }
            //들어갈 자리 j-- 보정 값 +1
            clone[j+1] = newMember;
        }
        return clone;
    }
}

전체 코드

package udemyjavascript;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.concurrent.ThreadLocalRandom;

public class SortEx01 {
	public static void main(String[] args) {
		ThreadLocalRandom current = ThreadLocalRandom.current();
		Integer[] array = current.ints(0,300).distinct().limit(10).boxed().toArray(Integer[]::new);
		System.out.println(array.getClass().getSimpleName()+"   "+ Arrays.toString(array));
		
		//정렬들 저장용
		List<SortStategy<Integer>> list = new ArrayList<>();
		list.add(new BubbleSort());
		list.add(new BubbleSortOp());
		list.add(new SelectionSort());
//		list.add(new InsertSort());
		
		for(SortStategy<Integer> sort : list) 
			System.out.printf("%-20s  %s%n",sort.getClass().getSimpleName(),
					Arrays.toString(sort.sort(array)));
	}
	
	static interface SortStategy<T>{
		T[] sort(T[] arr);
		//자리 바꿈 메서드
		default void swap(Integer[] clone, int i, int j) {
			Integer tmp = clone[i];
			clone[i] = clone[j];
			clone[j] = tmp;
		}
	}
	
	static class BubbleSort implements SortStategy<Integer>{
		static int cnt = 0;
		
		public Integer[] sort(Integer[] arr) {
			Integer[] clone = arr.clone();
			
			for(int i=0;i<clone.length-1;i++) {// n -1 번 수행
				for(int j=1;j<clone.length-i;j++) {
					cnt++;
					if(clone[j]<clone[j-1]) {
						swap(clone, j-1, j);
					}
				}
			}
			System.out.print("버블소트 cnt("+cnt+")");
			return clone;
		}
	}
	static class BubbleSortOp implements SortStategy<Integer>{
		Boolean noSwap = false;
		static int cnt = 0;
		
		public Integer[] sort(Integer[] arr) {
			Integer[] clone = arr.clone();
			
			for(int i=0;i<clone.length-1;i++) {// n -1 번 수행용 반복문
				noSwap = true;
				for(int j=1;j<clone.length-i;j++) {//자리바꿈 루프
					cnt++;
					if(clone[j]<clone[j-1]) {
						noSwap = false; // 자리바꿈이 한 번이라도 수행됐다.
						swap(clone, j-1, j);
					}
				}
				if(noSwap) break; //자리 바꿈이 수행된적이 없으면 수행용 반복은 의미없음
			}
			System.out.print("버블소트 최적화 cnt("+cnt+")");
			return clone;
		}
	}
	
	//버블 정렬보다 나은 점은 스왑수 최소화, i루프 마다 단 한번의 스왑만 발생
	static class SelectionSort implements SortStategy<Integer>{
		public Integer[] sort(Integer[] arr) {
			Integer[] clone = arr.clone();
			for(int i=0;i<clone.length-1;i++) {
				for(int j=i+1;j<clone.length;j++) {
					if(Integer.compare(clone[i], clone[j])>0) {
						swap(clone, i, j);
					}
				}
			}
			return clone;
		}
	}
	
	static class InsertSort implements SortStategy<Integer>{
		//논리적으로 순회 마다 작은 서브배열을 만든다고 가정한다.
		//1부터 시작
		public Integer[] sort(Integer[] arr) {
			Integer[] clone = arr.clone();
			//배열이 단 한개는 이미 정렬된 것이다. (논리적 배열)
			for(int i = 1;i<clone.length;i++) {
				//배열 shift 하는 동안 값 손실 때문이 임시 저장
				Integer newMember = clone[i];
				Integer j = i-1;
				//새로운 멤버 clone[i]
				for(;j>=0 && newMember < clone[j];j--) {
					clone[j+1] = clone[j];
				}
				//들어갈 자리 j-- 보정 값 +1
				clone[j+1] = newMember;
			}
			return clone;
		}
	}
}

Integer[]   [297, 76, 286, 161, 206, 20, 61, 160, 3, 9]
버블소트 cnt(45)BubbleSort            [3, 9, 20, 61, 76, 160, 161, 206, 286, 297]
버블소트 최적화 cnt(45)BubbleSortOp          [3, 9, 20, 61, 76, 160, 161, 206, 286, 297]
SelectionSort         [3, 9, 20, 61, 76, 160, 161, 206, 286, 297]

정렬 속도 비교

https://www.toptal.com/developers/sorting-algorithms

Sorting Algorithms Animations

Animation, code, analysis, and discussion of 8 sorting algorithms on 4 initial conditions.

www.toptal.com

저작자표시

'자료구조&알고리즘' 카테고리의 다른 글

달리기 경주 (0)	2023.07.14

개발 다이어리