알고리즘(4) - 정렬

목차

4-1. 선택 정렬

4-2. 버블 정렬

4-3. 삽입 정렬

4-4. 석차 구하기 

4-5. 이분 검색 

4-1. 선택 정렬

> 10개의 수치 자료를 입력 받아 배열에 저장한 후, 저장된 자료를 오름차순으로 정렬하는 코드 작성.

내 코드(java)

package Test.java;
import java.util.*;
 
public class TestMain {
 
    public static void main(String[] args) {
        
        Scanner scn = new Scanner(System.in);
        int[] input = new int[10];    //입력값 배열
        int i=0,j=0, cmp=5,temp=0,temp2=0;
        
        for(i=0;i<input.length;i++)
            input[i]=scn.nextInt();
        
        for(i=0;i<input.length-1;i++) {    //비교를 위해 input배열길이 -1번 반복
            cmp=input[i];
            temp=i;
            for(j=i; j< input.length -1; j++) {        //배열길이 -1번 반복
                if(cmp>input[j+1]) {        //비교값 input[i]가 input[j+1]보다 크면
                    cmp=input[j+1];            //비교값을 input[j+1]로 갱신
                    temp=j+1;                
                }                            //input[i]를 제외한 숫자 중 가장 작은 값이 cmp
            }                                //cmp의 인덱스는 temp에 저장
            input[temp]=input[i];            
            input[i]=cmp;        //20번줄 조건문에 true가 한번이라도 없었으면             
        }
        for(i=0;i<input.length;i++)
            System.out.print(input[i]+" ");
    }
}

*틀렸던 부분 : 

> for문에 j<input.length를 j<(input.length-1)로 입력. 변수 초기화에서 이미 설정해둔 반복횟수인데 또 설정했기 때문.

 

교재 코드(C)

#include "pch.h"
#include <iostream>
#include <stdio.h>
#define _CRT_SECURE_NO_WARNINGS 
 
int main() {
    int m,i,j,k,x;
    int data[10];
    m = -1;
 
    do {
        m++;
        scanf("%d", &data[m]);
    } while (m < 9);
    i = -1;
 
    do {
        i++;
        j = i;
        do {
            j++;
            if (data[i] > data[j]) {
                k = data[i];
                data[i] = data[j];
                data[j] = k;
            }
        } while (j < 9);
    } while (i < 8);
 
    for (x = 0; x <= 9; x++)
        printf("%d ", data[x]);
}

***교재 잘못쓰셨네... 뜯어보면 선택정렬이 아님

입력값 : 9 8 7 6 5 4 3 2 1 0

출력값 : 0 1 2 3 4 5 6 7 8 9

 

맨 위로

4-2. 버블 정렬 

> 입력받은 값을 버블정렬을 이용하여 오름차순 정렬

내 코드(java)

package Test.java;
import java.util.*;
 
public class TestMain {
 
    public static void main(String[] args) {
        
        Scanner scn = new Scanner(System.in);
        int i=0,j=0,temp=0;        
        
        System.out.print("버블정렬로 정렬할 정수를 입력하세요");
        String str = scn.next();            //문자열로 정수 입력
        int in[]=new int[str.length()];        //정수배열 선언
        
        for(i=0; i<in.length;i++)
            in[i]=str.charAt(i)-'0';        //입력된 문자열을 정수 배열에 저장
        
        for(i=0; i<in.length-1; i++) {
            for(j=0;j<in.length-1;j++) {
                if(in[j]>in[j+1]) {
                    temp=in[j];
                    in[j]=in[j+1];
                    in[j+1]=temp;
                }                    
            }
        }
        
        for(i=0; i<in.length;i++)
            System.out.print(in[i]+ " ");        //정렬된 정수를 출력
    }
}

*틀렸던 부분 : 

> 19번 줄 j초기값을 i로넣었음 = 선택정렬과 혼동

 

교재 코드(C)

#include "pch.h"
#include <iostream>
#include <stdio.h>
#define _CRT_SECURE_NO_WARNINGS 
 
int main() {
    int n, i, j, k;
    int data[10];
    n = -1;
 
    do {
        n++;
        scanf("%d", &data[n]);
    } while (n < 9);
 
    i = -1;
 
    do {
        i++;
        j = -1;
        do {
            j++;
            if (data[j] > data[j + 1]) {
                k = data[j];
                data[j] = data[j + 1];
                data[j + 1] = k;
            }
        } while (j < 8 - i);
    } while (i < 8);
 
    for (int x = 0; x <= 9; x++) {
        printf("%d ", data[x]);
    }
}

입력값 : 9 8 7 6 5 4 3 2 1 0

출력값 : 0 1 2 3 4 5 6 7 8 9

 

맨 위로

 

4-3. 삽입 정렬 

> 입력받은 값을 삽입정렬을 이용하여 오름차순 정렬

내 코드(java)

package Test.java;
import java.util.*;
 
public class TestMain {
 
    public static void main(String[] args) {
        
        Scanner scn = new Scanner(System.in);
        int i=0,j=0,k=0,chc=0,temp=0;        
        
        System.out.print("삽입 정렬로 정렬할 정수를 입력하세요");
        String str = scn.next();            //문자열로 정수 입력
        int in[]=new int[str.length()];        //정수배열 선언
        
        for(i=0; i<in.length;i++)
            in[i]=str.charAt(i)-'0';        //입력된 문자열을 정수 배열에 저장
        
        for(i=1; i<in.length; i++) {        //배열길이 -1만큼 반복
            chc=in[i];                        //기준값 저장
            for(j=(i-1);j>=0;j--) {
                if(in[j]>chc)        //기준값 보다 크면 다음값과 교환
                    in[j+1]=in[j];        
                else                //기준값 보다 작으면 반복 종료
                    break;
            }
            in[j+1]=chc;        //j위치에 기준갑 저장
        }
        
        for(i=0; i<in.length;i++)
            System.out.print(in[i]+ " ");        //정렬된 정수를 출력
    }
}

*틀렸던 부분 : 

> 거의 손 못대고 보고품

 

교재 코드(C)

#include "pch.h"
#include <iostream>
#include <stdio.h>
#define _CRT_SECURE_NO_WARNINGS 
 
int main() {
    int j, i, k, key;
    int a[10];
    j = -1;
 
    do {
        j++;
        scanf("%d ", &a[j]);
    } while (j < 9);
    
    for (i = 1; i <= 9; i++) {
        key = a[i];
        for (k = i - 1; k >= 0; k--) {
            if (a[k] > key)
                a[k + 1] = a[k];
            else
                break;
        }
        a[k + 1] = key;        
    }
 
    for (i = 0; i <= 9; i++)
        printf("%d ", a[i]);
}

입력값 : 54321

출력값 : 12345

 

맨 위로

 

4-4. 석차 구하기

> 10명의 학생에 대한 중간고사 점수의 석차를 구하는 코드 작성

 

내 코드(java)

package Test.java;
import java.util.*;
 
public class TestMain {
 
    public static void main(String[] args) {
        
        Scanner scn = new Scanner(System.in);
        int i=0,j=0,k=0,chc=0,temp=0;        
        int scr[]=new int[10];        //점수배열 선언
        int rnk[]=new int[10];        //석차배열 선언
        
        for(i=0;i<10;i++) {        //배열 초기화
        scr[i]=1;
        rnk[i]=1;
        }        
        
        for(i=0;i<10;i++) {
        System.out.print((i+1)+"번째 점수 : ");
        scr[i]=scn.nextInt();
        }
 
        for(i=0;i<10;i++) {
            for(j=0;j<10;j++) {
                if(scr[i]<scr[j])
                    rnk[i]++;
            }
        }
 
        System.out.print("점수 : ");
        for(i=0;i<10;i++)
            System.out.print(scr[i]+" ");
        
        System.out.println(" ");
        System.out.print("석차 : ");
        for(i=0;i<10;i++)
            System.out.print(rnk[i]+"  ");
    }
}
 

*틀렸던 부분 : 

> 배열 초기화를 안함(13~15행 누락)

교재 코드(C)

#include "pch.h"
#include <iostream>
#include <stdio.h>
#define _CRT_SECURE_NO_WARNINGS 
 
int main() {
    int m, n, i, j;
    int jumsu[10], rank[10];
 
    m = -1;
 
    do {
        m++;
        scanf("%d ", &jumsu[m]);
    } while (m < 9);
    n = 9;
    i = 0;
    while (i <= n) {
        rank[i] = 1;
        i++;
    }
    i = 0;
    while (i <= n) {
        j = 0;
        while (j <= n) {
            if (jumsu[i] < jumsu[j])
                rank[i]++;
            j++;
        }
        i++;
    }
    for (int x = 0; x < 10; x++)
        printf("%d ", jumsu[x]);
    printf("\n");
    for (int x = 0; x < 10; x++)
        printf("%d ", rank[x]);    
}

입력값 : 70 80 90 70 80 90 70 80 90 70

출력값 : 70 80 90 70 80 90 70 80 90 70

7 4 1 7 4 1 7 4 1 7

 

맨 위로

 

4-5. 이분 검색 

> 키보드로 입력 받은 번호에 대한 점수를 DATA 배열에서 찾아 출력하는 코드를 작성

> 단, DATA[2][10] 배열에는 번호와 점수가 들어있다고 가정하고, 찾는 자료가 없을 경우 자료와 함께 "NOT FOUND" 출력

내 코드(java)

*틀렸던 부분 : 

 

교재 코드(C)

#include "pch.h"
#include <iostream>
#include <stdio.h>
#define _CRT_SECURE_NO_WARNINGS 
 
int main() {
    int j, L, h, m;
    int data[2][10] = { { 1,2,3,4,5,6,7,8,9,10 }, { 100,66,25,88,90,65,87,86,58,99 } };
 
    scanf("%d", &j);
    L = 0;
    h = 9;
 
    while (1) {
        if (L <= h) {
            m = (L + h) / 2;
            if (j == data[0][m]) {
                printf("%d %d\n", j, data[1][m]);
                break;
            }
            if (j < data[0][m])
                h = m - 1;
            else
                L = m - 1;
        }
        else {
            printf("%d NOT FOUND", j);
            break;
        }        
    }
}

입력값 : 

출력값 : 

 

맨 위로