09일차_거품정렬,선택정렬,삽입정렬

---------------------------------
정렬 알고리즘

1. 원소들을 번호순이나 사전 순서와 같이 일정한 순서대로 열거하는 알고리즘

2.
거품 정렬, 삽입 정렬, 선택 정렬....

3. 거품 정렬(bubble sort) : 두 인접한 원소를 검사하여 정렬하는 방법
55 07 78 12 42  -> 원본 상태

[55 07] 78 12 42  첫 번째 패스
07 [55 78] 12 42
07 55 [78 12] 42
07 55 12 [78 42]
07 55 12 42 [78]

[07 55] 12 42  - 78  두 번째 패스 (가장 오른쪽 값은 제외)
07 [55 12] 42  - 78
07 12 [55 42]  - 78
07 12 42 [55]  - 78

[07 12] 42  - 55 78  세 번째 패스 (오른쪽 값 두 개는 제외)
07 [12 42]  - 55 78
07 12 [42]  - 55 78

[07 12]  - 42 55 78  네 번째 패스 (오른쪽 값 세 개는 제외)
07 [12]  - 42 55 78

07 12 42 55 78 => 정렬 끝

 

문제) 거품 정렬 알고리즘
4 5 3 1 2

1회전 -> ? ? ? ? 5
2회전 -> ? ? ? 4 5
3회전 -> ? ? 3 4 5
4회전 -> ? 2 3 4 5
정렬 완료 -> 1 2 3 4 5

 

//Sample60.java
package com.test;

public class Sample60 {

 public static void main(String[] args) {

  int[] array = {4, 5, 3, 1, 2};
  
  //정렬 과정 추가
  //1. 비교 if(조건)
  //2. 치환  array[n] <= array[n+1];
  //3. 반복 for(초기식;조건식;증감식)
  
  //a->0부터 (n-2)까지
  //b->1부터 (n-1)까지->a+1
  /*
  if (array[0] > array[1]) {
   int temp = array[1];
   array[1] = array[0];
   array[0] = temp;
  }
  if (array[1] > array[2]) {
   int temp = array[2];
   array[2] = array[1];
   array[1] = temp;
  }
  if (array[2] > array[3]) {
   int temp = array[3];
   array[3] = array[2];
   array[2] = temp;
  }
  if (array[3] > array[4]) {
   int temp = array[4];
   array[4] = array[3];
   array[3] = temp;
  }
  */
  int n = array.length;
  for (int a=0; a<n-1; ++a) {
   if (array[a] > array[a+1]) {
    int temp = array[a+1];
    array[a+1] = array[a];
    array[a] = temp;
   }
  }
  
  for (int a=0; a<array.length; ++a) {
   System.out.printf(" %d", array[a]);
  }
  System.out.println();
  
 }

}

 

 

거품 정렬 구현 코드
//Sample61.java
package com.test;

public class Sample61 {

 public static void main(String[] args) {

  int[] array = {4, 5, 3, 1, 2};
  
  //정렬 과정 추가
  //1. 비교 if(조건)
  //2. 치환  array[n] <= array[n+1];
  //3. 반복 for(초기식;조건식;증감식)

  //n이 5인 경우 4회전, 10인 경우 9회전
  //n->length부터 2까지
  //a->0부터 (n-2)까지
  //b->1부터 (n-1)까지->a+1
  for (int n=array.length; n>=2; --n) {
   for (int a=0; a<n-1; ++a) {
    if (array[a] > array[a+1]) {
     int temp = array[a+1];
     array[a+1] = array[a];
     array[a] = temp;
    }
   }
  }
  
  for (int a=0; a<array.length; ++a) {
   System.out.printf(" %d", array[a]);
  }
  System.out.println();
  
 }

}

 

 

//Sample62.java
package com.test;

public class Sample62 {

 public static void main(String[] args) {

  int[] array = {4, 5, 6, 3, 7, 1, 2};
  
  //정렬 과정 추가
  //1. 비교 if(조건)
  //2. 치환  array[n] <= array[n+1];
  //3. 반복 for(초기식;조건식;증감식)

  //n이 5인 경우 4회전, 10인 경우 9회전
  //n->1부터 1씩 증가하도록 작성
  //a->0부터 (n-2)까지
  //b->1부터 (n-1)까지->a+1
  for (int n=1; n<array.length ;++n) {
   for (int a=0; a<array.length-n; ++a) {
    if (array[a] > array[a+1]) {
     int temp = array[a+1];
     array[a+1] = array[a];
     array[a] = temp;
    }
   }
  }
  
  for (int a=0; a<array.length; ++a) {
   System.out.printf(" %d", array[a]);
  }
  System.out.println();
  
 }

}

 

-------------------------------------------------

//Sample63.java
package com.test;

public class Sample63 {

 public static void main(String[] args) {

  int[] array = {4, 5, 3, 1, 2};
  
  //정렬 과정 추가
  //1. 비교 if(조건)
  //2. 치환  array[n] <= array[n+1];
  //3. 반복 for(초기식;조건식;증감식)

  //n이 5인 경우 4회전, 10인 경우 9회전
  //n->1부터 1씩 증가하도록 작성
  //a->0부터 (n-2)까지
  //b->1부터 (n-1)까지->a+1
  for (int n=1; n<array.length ;++n) {
   for (int a=0; a<array.length-n; ++a) {
    if (array[a] > array[a+1]) {
     int temp = array[a+1];
     array[a+1] = array[a];
     array[a] = temp;
    }
   }
   
   //중간 결과 출력
   for (int a=0; a<array.length; ++a) {
    if (a == array.length-n) {
     System.out.print(" <");
    }
    System.out.printf(" %d", array[a]);
   }
   System.out.println();   
  }

  //최종 결과 출력
  System.out.println("--------------------");
  for (int a=0; a<array.length; ++a) {
   System.out.printf(" %d", array[a]);
  }
  System.out.println();
  
 }

}

 

문제) 외부에서 여러개의 숫자를 입력 받은 후에, 정렬(거품정렬) 시켜서 출력.
입력 범위(2~n)?5
정수1?5
정수2?2
정수3?3
정수4?1
정수5?4

정렬 결과 : 1 2 3 4 5

 

---------------------------------------------------

4. 선택 정렬(selection sort) : 전체 리스트에서 최소값을 가장 앞에 위치시키는 정렬 방법. 비교는 가장 앞에 있는 값과 나머지 값들을 비교.
55 07 78 12 42  -> 원본 상태

[55] [07] 78 12 42 첫 번째 패스
[07] 55 [78] 12 42
[07] 55 78 [12] 42
[07] 55 78 12 [42]
[07] 55 78 12 42

07 - [55] [78] 12 42 두 번째 패스 (가장 왼쪽 값은 제외)
07 - [55] 78 [12] 42
07 - [12] 78 55 [42]
07 - [12] 78 55 42

07 12 - [78] [55] 42 세 번째 패스 (왼쪽 두 개는 제외)
07 12 - [55] 78 [42]
07 12 - [42] 78 55

07 12 42 - [78] [55] 네 번째 패스 (왼쪽 세 개는 제외)
07 12 42 - [55] 78

07 12 42 55 78 -> 정렬 결과

 

문제) 선택 정렬 알고리즘
4 5 3 1 2

1회전 -> 1 ? ? ? ?
2회전 -> 1 2 ? ? ?
3회전 -> 1 2 3 ? ?
4회전 -> 1 2 3 4 ?
정렬 완료 -> 1 2 3 4 5

 

//Sample64.java
package com.test;

public class Sample64 {

 public static void main(String[] args) {

  int[] array = {4, 5, 3, 1, 2};
  
  //정렬 과정 추가
  //1. 비교 if(조건)
  //2. 치환  array[n] <= array[n+1];
  //3. 반복 for(초기식;조건식;증감식)
  
  /*
  if (array[0] > array[1]) {
   int temp = array[1];
   array[1] = array[0];
   array[0] = temp;   
  }
  if (array[0] > array[2]) {
   int temp = array[2];
   array[2] = array[0];
   array[0] = temp;   
  }
  if (array[0] > array[3]) {
   int temp = array[3];
   array[3] = array[0];
   array[0] = temp;   
  }
  if (array[0] > array[4]) {
   int temp = array[4];
   array[4] = array[0];
   array[0] = temp;   
  }
  */
  
  //n => 갯수
  //a => 0
  //b => 1 ~ (n-1)
  int n=array.length;
  int a=0;
  for (int b=1; b<n; ++b) {
   if (array[a] > array[b]) {
    int temp = array[b];
    array[b] = array[a];
    array[a] = temp;   
   }
  }
  
  for (int c=0; c<array.length; ++c) {
   System.out.printf(" %d", array[c]);
  }
  System.out.println();  
  
 }

}

 

 

선택 정렬 구현 코드
//Sample65.java
package com.test;

public class Sample65 {

 public static void main(String[] args) {

  int[] array = {4, 5, 3, 1, 2};
  
  //정렬 과정 추가
  //1. 비교 if(조건)
  //2. 치환  array[n] <= array[n+1];
  //3. 반복 for(초기식;조건식;증감식)
  
  //n => 갯수(array.length)
  //a => 0 ~ (n-2)
  //b => (a+1) ~ (n-1)
  for (int a=0; a<array.length-1; ++a) {
   for (int b=(a+1); b<array.length; ++b) {
    if (array[a] > array[b]) {
     int temp = array[b];
     array[b] = array[a];
     array[a] = temp;   
    }
   }

   //중간 결과 출력
   for (int c=0; c<array.length; ++c) {
    if (c == (a+1)) {
     System.out.print(" <");
    }
    System.out.printf(" %d", array[c]);
   }
   System.out.println(); 

  }
  
  for (int c=0; c<array.length; ++c) {
   System.out.printf(" %d", array[c]);
  }
  System.out.println();  
  
 }

}

 

 

문제) 외부에서 여러개의 숫자를 입력 받은 후에, 정렬(선택정렬) 시켜서 출력.

입력 범위(2~n)?5
정수1?5
정수2?2
정수3?3
정수4?1
정수5?4

정렬 결과 : 1 2 3 4 5

 

 

 

-----------------------------------
삽입 정렬(insertion sort)

1. 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘

55 07 78 12 42  -> 원본 상태

55 (07) 78 12 42 -> key        첫 번째 패스
[55] 07 78 12 42 - [key=07]
55 [55] 78 12 42
[07] 55 78 12 42 <- [key=07]
[07] 55 78 12 42

07 55 (78) 12 42 -> key       두 번째 패스
07 [55] 78 12 42 - [key=78]
[07] 55 78 12 42 - [key=78]
07 55 [78] 12 42 <- [key=78]
07 55 [78] 12 42

07 55 78 (12) 42 -> key      세 번째 패스
07 55 [78] 12 42 - [key=12]
07 55 78 [78] 42
07 [55] 78 78 42 - [key=12]
07 55 [55] 78 42
[07] 55 55 78 42 - [key=12]
07 [12] 55 78 42 <- [key=12]
07 [12] 55 78 42

07 12 55 78 (42) -> key     네 번째 패스
문제) 선택 정렬의 네 번째 패스에서 나머지 숫자 배열을 채웁니다.

 

------------------------------------------
여러명의 점수를 입력 받고, 점수가 높은 순으로 등수 부여해서 출력하는 과정 작성. 이름과 점수는 별도의 배열에 저장.
실행 예)
입력 범위(2~n)?3
이름 점수(1)?kim 30
이름 점수(2)?choi 70
이름 점수(3)?park 60
---------------------
1등 choi 70
2등 park 60
3등 kim 30
---------------------

//Sample48.java
package com.test;

import java.util.Scanner;

public class Sample48 {
 
 public static void main(String[] args) {
  
  //여러명의 이름, 점수 입력 -> 배열 2개
  Scanner sc = new Scanner(System.in);
  System.out.print("인원수(n)?");
  int size = sc.nextInt();
  String[] names = new String[size];
  int[] scores = new int[size];
  
  for (int i=0; i<names.length; ++i) {
   System.out.printf("이름 점수(%d)?", (i+1));
   names[i] = sc.next();
   scores[i] = sc.nextInt();
  }
  sc.close();
  
  //점수가 높은 순으로 정렬 (내림차순)
  //n회전 반복
  //1회전 반복
  //비교대상
  //치환
  for (int b=0; b<scores.length-1; ++b) {
   for (int a=0; a<scores.length-1-b; ++a) {
    if (scores[a] < scores[a+1]) {
     String temp1 = names[a+1];
     names[a+1] = names[a];
     names[a] = temp1;
     int temp2 = scores[a+1];
     scores[a+1] = scores[a];
     scores[a] = temp2;
    }
   }
  }
  
  //배열->출력
  for (int b=0; b<scores.length; ++b) {
   System.out.printf("%d등 %s %d %n"
       , (b+1)
       , names[b]
       , scores[b]);
  }
  System.out.println();

 }

}

 

 

문제) 위의 결과에서 정렬 알고리즘을 선택 정렬로 수정할 것.
//Sample49.java
package com.test;

import java.util.Scanner;

public class Sample49{
 
 
 public static void main(String[] args) {
  
  //여러명의 이름, 점수 입력 -> 배열 2개
  Scanner sc = new Scanner(System.in);
  System.out.print("인원수(n)?");
  int size = sc.nextInt();
  String[] names = new String[size];
  int[] scores = new int[size];
  
  for (int i=0; i<names.length; ++i) {
   System.out.printf("이름 점수(%d)?", (i+1));
   names[i] = sc.next();
   scores[i] = sc.nextInt();
   
  }
  sc.close();
  
  //문제) 점수가 높은 순으로 정렬 (선택정렬, 내림차순)
  

 

  
  //배열->출력
  for (int b=0; b<scores.length; ++b) {
   System.out.printf("%d등 %s %d %n"
       , (b+1)
       , names[b]
       , scores[b]);
  }
  System.out.println();

 }

}

 

 

 

-------------------------------------------
과제) 삽입 정렬 순서도(삽입정렬_순서도.png)를 완성하고, Java 프로그램으로 작성.

 

 

 

 

-------------------------------------------
요약

1. 정렬 알고리즘
2. 거품 정렬 : 인접한 두 숫자 비교, 큰 값 오른쪽.
3. 선택 정렬 : 기준값과 나머지를 비교. 작은 값 왼쪽.
3. 삽입 정렬 : key 변수 필요. key 변수에 기준값 저장. key와 나머지 값과 비교. 자기 위치를 찾아서 삽입.

-------------------------------------------