KB IT’s Your Life 4기 - Java 알고리즘 8일차

정렬

버블정렬

  • 가장 단순
  • 가장 느림

image

//이 경우, index가 뒤에서부터 비교함.
static void bubbleSort(int[] a, int n){
   for(int i=0; i< n-1; i++){
      for(int j=n-1; j>i; j--){ //j는 비교 시작 위치
         if(a[j-1] > a[j]) swap(a, j-1, j);
      }
   }
}

전체 코드

package 버블정렬;

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		System.out.println("버블정렬");
		System.out.println("요소수: ");
		
		int nx = sc.nextInt();
		int[] x = new int[nx];
		
		for(int i=0; i<nx; i++) {
			System.out.println("x[" + i + "]: ");
			x[i] = sc.nextInt();
		}
		
		bubblesort(x, nx);
		
		System.out.println("버블정렬 결과");
		for(int i=0; i<nx; i++) {
			System.out.println("x[" + i + "]: "+ x[i]);
		}
		
	}

	private static void bubblesort(int[] x, int nx) {
		   for(int i=0; i< nx-1; i++){
			      for(int j=nx-1; j>i; j--){ //j는 비교 시작 위치
			         if(x[j-1] > x[j]) swap(x, j-1, j);
			      }
			   }		
	}

	private static void swap(int[] x, int i, int j) {
		int temp = x[i];
		x[i] = x[j];
		x[j] = temp;
	}
}

버블정렬
요소수: 7
x[0]: 6
x[1]: 4
x[2]: 3
x[3]: 7
x[4]: 1
x[5]: 9
x[6]: 8
버블정렬 결과
x[0]: 1
x[1]: 3
x[2]: 4
x[3]: 6
x[4]: 7
x[5]: 8
x[6]: 9
  • 변수를 static으로 정의하는 경우, 변화
package 버블정렬;

import java.util.Scanner;

public class Main {
	static int nx;
	static int[] x;
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		System.out.println("버블정렬");
		System.out.print("요소수: ");
		
		nx = sc.nextInt();
		x = new int[nx];
		
		for(int i=0; i<nx; i++) {
			System.out.print("x[" + i + "]: ");
			x[i] = sc.nextInt();
		}
		
		bubblesort(); //변수 제거
		
		System.out.println("버블정렬 결과");
		for(int i=0; i<nx; i++) {
			System.out.println("x[" + i + "]: "+ x[i]);
		}
		
	}

	private static void bubblesort() { //변수 제거
		   for(int i=0; i< nx-1; i++){
			      for(int j=nx-1; j>i; j--){ //j는 비교 시작 위치
			         if(x[j-1] > x[j]) swap(j-1, j);
			      }
			   }		
	}

	private static void swap(int i, int j) { //변수 제거
		int temp = x[i];
		x[i] = x[j];
		x[j] = temp;
	}
}

선택 정렬

  • 비교 횟수가 버블과 같음
  • 교환이 한 번만 이루어짐.
  • 버블보다 아주 조금 더 빠를 뿐.

image

삽입 정렬

  • 복사 횟수가 많음.

image

package j1158;

import java.util.Scanner;

public class Main {
	static int nx;
	static int[] x;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		nx = sc.nextInt();
		x = new int[nx];

		for (int i = 0; i < nx; i++) {
			x[i] = sc.nextInt();
		}

		insertionSort();
	}

	private static void showArray() {
		for (int z = 0; z < nx; z++) {
			System.out.print(x[z] + " ");
		}
		System.out.println();

	}

	private static void insertionSort() {
		for (int i = 1; i < nx; i++) {
			int j;
			int temp = x[i];
			for (j = i; j > 0 && x[j - 1] > temp; j--) {
				x[j] = x[j - 1];
			}
			x[j] = temp;
			showArray();
		}
	}
}

퀵 정렬

  • 가장 빠른 정렬 알고리즘
  • 피벗을 중심으로 이등분함.
  • 재귀 함수가 필요 (1. 종료조건 / 2. 처리)
//팩토리얼
package 재귀호출;

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		System.out.println("숫자를 입력 ");

		int n = sc.nextInt();

		int ans = factorial(n);
		System.out.println(ans);
	}

	private static int factorial(int n) {
		if (n == 0)
			return 1;
		return n * factorial(n - 1);
	}

}

******암기하면, 코테 1/3 공부는 끝!!!******

//경우의 수 > 이거 암기!이해!
package 재귀호출;

public class 경우의수 {
	static int[] arr;
	static int[] result;
	static int n;

	public static void main(String[] args) {
		// 주어진 원소를 이용한 생성가능한 모든 경우의 수
		// {1,2,3} -> 111, 112, 113...(중복 허용)
		// {1,2,3} -> 123, 132, 213 , 231, 312, 321 (중복 허용X)
		// {1,2} -> (중복 허용) 11, 12, 21, 22 (중복허용X) 12, 21

		arr = new int[] { 1, 2, 3 }; // 원소 저장
		result = new int[arr.length]; // 답 저장

		n = 3; // 추출의 개수

		recur(0);

	}

	private static void recur(int depth) {
		if (depth == n) { // 종료조건
			print();
			return;
		}
		// 처리코드(깊이의 숫자 위치에 i를 저장)
		for (int i = 0; i < arr.length; i++) {
			result[depth] = arr[i];
			recur(depth+1);
		}

	}

	private static void print() {
		for (int i : result) {
			System.out.print(i); // 가로로 붙여서 출력
		}
		System.out.println(); // 빈 줄 생성

	}
}


//결과
111
112
113
121
122
123
131
132
133
211
212
213
221
222
223
231
232
233
311
312
313
321
322
323
331
332
333


//중복 허용하지 않는 경우의 수 (숟가락 얹기) = 순열

package 재귀호출;

public class 경우의수2 { // 중복 허용하지 않는 경우
	static int[] arr;
	static int[] result;
	static int n;
	static boolean[] visited; // (추가) 사용 여부 저장

	public static void main(String[] args) {
		// 주어진 원소를 이용한 생성가능한 모든 경우의 수
		// {1,2,3} -> 111, 112, 113...(중복 허용)
		// {1,2,3} -> 123, 132, 213 , 231, 312, 321 (중복 허용X)
		// {1,2} -> (중복 허용) 11, 12, 21, 22 (중복허용X) 12, 21

		arr = new int[] { 1, 2, 3 }; // 원소 저장
		result = new int[arr.length]; // 답 저장
		visited = new boolean[arr.length]; //(추가)

		n = 3; // 추출의 개수

		recur(0);

	}

	private static void recur(int depth) {
		if (depth == n) { // 종료조건
			print();
			return;
		}
		// 처리코드(깊이의 숫자 위치에 i를 저장)
		for (int i = 0; i < arr.length; i++) {
			if (visited[i] == false) { //(추가)
				result[depth] = arr[i];
				visited[i] = true; //(추가)
				recur(depth + 1);
				visited[i] = false; //(추가)
			}
		}

	}

	private static void print() {
		for (int i : result) {
			System.out.print(i); // 가로로 붙여서 출력
		}
		System.out.println(); // 빈 줄 생성

	}
}


package 재귀호출;

public class 경우의수3 { //숫자는 1번씩 사용. 2개 숫자만 추출
	static int[] arr;
	static int[] result;
	static int n;
	static boolean[] visited; // 사용 여부 저장

	public static void main(String[] args) {
		// 주어진 원소를 이용한 생성가능한 모든 경우의 수
		// {1,2,3} -> 111, 112, 113...(중복 허용)
		// {1,2,3} -> 123, 132, 213 , 231, 312, 321 (중복 허용X)
		// {1,2} -> (중복 허용) 11, 12, 21, 22 (중복허용X) 12, 21

		arr = new int[] { 1, 2, 3 }; // 원소 저장
		result = new int[arr.length-1]; // 답 저장 =int[2]
		visited = new boolean[arr.length];

		n = 2; // 추출의 개수

		recur(0);

	}

	private static void recur(int depth) {
		if (depth == n) { // 종료조건
			print();
			return;
		}
		// 처리코드(깊이의 숫자 위치에 i를 저장)
		for (int i = 0; i < arr.length; i++) {
			if (visited[i] == false) {
				result[depth] = arr[i];
				visited[i] = true;
				recur(depth + 1);
				visited[i] = false;
			}
		}

	}

	private static void print() {
		for (int i : result) {
			System.out.print(i); // 가로로 붙여서 출력
		}
		System.out.println(); // 빈 줄 생성

	}
}

드디어 퀵정렬

package 퀵정렬;

import java.util.Scanner;

public class Main {
	static int nx;
	static int[] x;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		System.out.println("퀵정렬");
		System.out.print("요솟수: ");
		nx = sc.nextInt();
		x = new int[nx];
		
		for(int i=0; i<nx; i++) {		
			System.out.print("x["+ i +"]: ");
			x[i] = sc.nextInt();
		}
		
		quickSort(0, nx-1);
		
		System.out.println("오름차순으로 정렬했습니다.");
		
		for(int i=0; i<nx; i++) {
			System.out.println("x["+i+"]="+x[i]);
		}
	}

	private static void quickSort(int left, int right) {
		int pl = left;
		int pr = right;
	
		int a = x[(pl+pr)/2];
		
		do {
			while(x[pl]<a) pl++;
			while(x[pr]>a) pr--;
			if(pl<=pr) {
				swap(pl++,pr--);
			}
		}while(pl<=pr);
		
		if(left <pr) {quickSort(left, pr);}
		if(pl < right) {quickSort(pl, right);}
		
	}

	private static void swap(int i, int j) {
		int temp = x[i];
		x[i] = x[j];
		x[j] = temp;
	}

}

병합정렬

  • 외부에 임시배열을 둠.(앞/뒤)
  • 각각 정렬 후 병합 (분할정복법)