[TIL] 배열 (2)

배열의 정렬

선택 정렬 Selection Sort

선택 정렬은 이름에 맞게 현재 위치에 들어갈 값을 찾아 정렬하는 배열이다.

시간 복잡도는 상당히 느린편이다,

 

기본 알고리즘

1) 정렬되지 않은 인덱스 맨 앞에서부터 이를 포함한 이 후의 배열 값 중 가장 작은 값으 찾아간다.

2) 가장 작은 값을 찾으면 그 값을 인덱스의 값과 바꿔준다.

3)다음 인덱스에서 위 과정을 반복한다.

비교 횟수 :  n(n-1)/2

비교 회전 수 :  n-1

package ex0730;
 
public class Selection_ex1 {
 
    public static void main(String[] args) {
        // selection sort
        int[] a = new int[] { 30, 27, 15, 60, 7, 21 };
        int t;
 
        System.out.print("source data : ");
        for (int n : a) {
            System.out.print(n + " ");
        }
        System.out.println();
/*
 * data
 * 1회전 : 0:1 0:2 0:3 0:4 0:5      //i=0;
 * 2회전 : 1:2 1:3 1:4 1:5           //i=1;  
 * 3회전 : 2:3 2:4 2:5               //i=2;
 * 4회전 : 3:4 3:5                 //i=3;
 * 5회전 : 4:5                     //i=4
 * 
 */
        for (int i = 0; i < a.length - 1; i++) { // 반복횟수 5번 i= 0,1,2,3,4 // 회전의 횟수 for문
            for (int j = i + 1; j < a.length; j++) {
                if (a[i] > a[j]) {// 내림 차순 오름 차순 변경은 부등호로 결정함
                    t = a[i];
                    a[i] = a[j];
                    a[j] = a[j] = t;
                }
            }
        }
        System.out.println("sort data : ");
        for (int n : a) {
            System.out.print(n + "  ");
        }
        System.out.println();
    }
 
}
/*
 source data : 30 27 15 60 7 21 
sort data : 
7  15  21  27  30  60 
 
 */
 

1) 선택 정렬 예시

인원수와 점수를 입력 받아 해당 점수의 석차를 구하는 정렬 프로그램

package ex0730;
 
import java.util.Scanner;
 
public class Selection_ex2 {
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int cnt;
 
        String[] name;
        int[] score;
        int[] rank;
 
        do {
            System.out.print("인원수?");
            cnt = sc.nextInt();
        } while (cnt < 1);
        // 인원수 만큼 배열 메모리 할당
        name = new String[cnt];
        score = new int[cnt];
        rank = new int[cnt];
 
        // 인원수 만큼 이름 , 점수 입력 받기
        for (int i = 0; i < cnt; i++) {
            System.out.print((i + 1) + "번째 이름?");
            name[i] = sc.next();
            System.out.print("  점수?");
            score[i] = sc.nextInt();
            rank[i] = 1; // 석차 초기값
        }
        // 석차 계산
        // 반드시 1등은 존재 // 석차는 초기값 1로 설정
 
        for (int i = 0; i < cnt - 1; i++) {
            for (int j = i + 1; j < cnt; j++) {
                if (score[i] < score[j]) {
                    rank[i]++;
                } else if (score[j] < score[i]) {
                    rank[j]++;
                }
            }
        }
 
        System.out.println("\n이름\t점수\t석차");
        for (int i = 0; i < cnt; i++) {
            System.out.print(name[i] + "\t");
            System.out.print(score[i] + "\t");
            System.out.print(rank[i] + "\n");
        }
        System.out.println();
        sc.close();
    }
 
}
/*
인원수?3
1번째 이름?a
  점수?3
2번째 이름?b
  점수?5
3번째 이름?c
  점수?4
 
이름    점수    석차
a    3    3
b    5    1
c    4    2
*/
 

버블 정렬 Bubble Sort

인접한 두 수를 비교하여 큰 수를 뒤로 보내는 간단한 정렬 알고리즘 이다,

 

기본 알고리즘

1) 정렬되지 않은 인덱스의 맨 앞에서 부터 이를 포함한 그 이후의 배열 값 중 가장 작은 값을 찾아간다.

2) 가장 작은 값을 찾으면, 그 값을 현재 인덱스의 값과 바꿔준다,.

3) 다음 인덱스에서도 반복한다.

package ex0730;
 
public class bubbleAd_Ex2 {
 
    public static void main(String[] args) {
        
        int[] a = new int[] { 30, 27, 15, 60, 7, 21 };
        int t;
        boolean flag;
        int pass;
 
        System.out.print("source data : ");
        for (int n : a) {
            System.out.print(n + " ");
        }
        System.out.println();
         // 버블 소트
        pass=1;
        do {
            flag=false;
            for(int i=0;i<a.length-pass;i++) {
                if(a[i]>a[i+1]) {
                    t=a[i]; a[i]=a[i+1]; a[i+1]=t;
                    flag=true;
                }
            }pass++;
        }while(flag);
            
        
        System.out.println("sort data : ");
        for (int n : a) {
            System.out.print(n + "  ");
        }
        System.out.println();
    }
 
}
/*
source data : 30 27 15 60 7 21 
sort data : 
7  15  21  27  30  60  
 */