삽입정렬

삽입정렬 개념

• 삽입정렬은 두 번째 자료부터 시작하여 그 앞(왼쪽) 자료들과 비교하여 삽입할 위치를 지정한 후 자료를 뒤로 옮기고 지정한 자리에 자료를 삽입하여 정렬하는 알고리즘 이다.
• 장점 : 레코드가 이미 정렬되어 있는 경우 매우 효율적이다.
• 단점 : 비교적 많은 레코드들의 이동을 포함하고 레코드의 수가 클 경우 적합하지 않다.
• 시간복잡도 : Best T(n) = O(n) , Worst T(n) = O(n^2)

참고 URL : https://www.w3resource.com/csharp-exercises/searching-and-sorting-algorithm/searching-and-sorting-algorithm-exercise-6.php

소스

#include<iostream>
using namespace std;

int main(){
    //freopen("input.txt", "rt" ,stdin);
    int i,j,temp;
    int array[10] = {1,10,5,8,7,6,4,3,2,9};
    for(i=0; i < 9; i++){
        j=i;
        while(array[j] > array[j+1]){
            temp = array[j];
            array[j] = array[j+1];
            array[j+1] = temp;
            j--;
        }
    }

    for(i=0;i<10;i++){
        printf("%d ", array[i]);
    }

    return 0;
}

소스2

public class insertSort {

    public static void main(String[] args) {

        int array[] = {1,10,5,8,7,6,4,3,2,9}; // 10개

        viewArray(array);

        System.out.println();
        int temp;
        int j=0;
        for(int i=1; i < array.length; i++){
            temp = array[i];
            j = i;
            while( (j>0) && (array[j-1] > temp) ){
                array[j] = array[j-1];
                j--;
            }
            array[j] =temp;
        }
        viewArray(array);
    }


    static public void viewArray(int array[]){

        for(int i=0; i < array.length; i++){
            System.out.printf(array[i] + " ");
        }

    }
}