기본정렬알고리즘(선택정렬, 버블정렬, 삽입정렬)

손코딩으로 나오거나 정보처리기사에서도 자주 나오는 기본 정렬 알고리즘

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

Sorting Algorithms Animations

위 사이트에서 알고리즘이 어떤 방식으로 진행되는지, 속도는 대략 어느 정도인지 한눈에 살펴볼 수 있다.

 

선택정렬

public static void main(String[] args) {
		//selection sort
		int[]num=new int[] {25,15,10,5,12,9,17,23,13,19};
		int t;
		
		System.out.print("Source data : ");
		for(int n:num) {
			System.out.printf("%5d",n);
		}
		System.out.println();
		
		
		//정렬
		for(int i=0;i<num.length-1;i++) {
			for(int j=i+1;j<num.length;j++) {
				if(num[i]>num[j]) {
					t = num[i];
					num[i]=num[j];
					num[j]=t;
				}
			}
		}

		System.out.print("Sort data : ");
		for(int n:num) {
			System.out.printf("%5d",n);
		}
		System.out.println();
		
	}

 

버블정렬

public static void main(String[] args) {
		//bubble sort
		int[]num=new int[] {25,15,10,5,12,9,17,23,13,19};
		int t;
		
		System.out.print("Source data : ");
		for(int i=0;i<num.length;i++) {
			System.out.printf("%5d",num[i]);
		}
		System.out.println();
		
		//정렬
		for(int i=1;i<num.length;i++) {	//1~9
			for(int j=0;j<num.length-1;j++) {	//i=1 j=0~8 i=2 j=0~7
				if(num[j]>num[j+1]) {
					t=num[j];
					num[j]=num[j+1];
					num[j+1]=t;
				}
			}
			System.out.println(i+"회전 : "+ Arrays.toString(num));
		}
		
		
		System.out.print("Sort data : ");
		for(int i=0;i<num.length;i++) {
			System.out.printf("%5d",num[i]);
		}
		System.out.println();

	}

 

개선된 버블정렬

public static void main(String[] args) {
		// 개선된 bubble sort
		int [] num= new int[] {10,20,15,30,35,45,50,60,55,53};
		int t,pass;
		boolean b;
		
		System.out.print("Source data : ");
		for(int i=0;i<num.length;i++) {
			System.out.printf("%5d",num[i]);
		}
		System.out.println();

		pass=1;
		do {
			b=false;
			for(int i=0;i<num.length-pass;i++) {
				if(num[i]>num[i+1]) {
					t=num[i]; num[i]=num[i+1]; num[i+1]=t;
					b=true;
				}
			}
			System.out.println(pass+"회전 : "+ Arrays.toString(num));
			
			pass++;
		}while(b);
		
		
		System.out.print("Sort data : ");
		for(int i=0;i<num.length;i++) {
			System.out.printf("%5d",num[i]);
		}
		System.out.println();
	}

 

삽입정렬

public static void main(String[] args) {
		// insertion sort

		int[] num = { 25, 15, 7, 5, 13, 10, 17, 16, 23, 12 };
		int i, j, key;

		System.out.print("Source data : ");
		for (int n : num) {
			System.out.printf("%5d", n);
		}
		System.out.println();

		for (i = 1; i < num.length; i++) {
			key = num[i];
			for (j = i - 1; j >= 0; j--) {
				if (key < num[j]) {
					num[j + 1] = num[j];
				} else {
					break;
				}
			}
			num[j + 1] = key;
		}

		System.out.print("Sort data : ");
		for (int n : num) {
			System.out.printf("%5d", n);
		}
		System.out.println();

	}