버블 정렬 / 삽입정렬

버블 정렬

첫째 항부터 마지막 항까지, 다음 index의 요소와 값을 비교해 더 큰 수를 뒤로 보낸다.
이렇게 처음부터 마지막까지 반복하면 1회이다.
따라서 시간복잡도는 O(n^2) 가 된다.
표본 수가 커지면 매우 비효율적인 정렬 방법.

✏️ 문제

* 설명
N개이 숫자가 입력되면 오름차순으로 정렬하여 출력하는 프로그램을 작성하세요.
정렬하는 방법은 버블정렬입니다.

* 입력
첫 번째 줄에 자연수 N(1<=N<=100)이 주어집니다.
두 번째 줄에 N개의 자연수가 공백을 사이에 두고 입력됩니다. 각 자연수는 정수형 범위 안에 있습니다.

* 출력
오름차순으로 정렬된 수열을 출력합니다.

🔍풀이

  public int[] solution(int n, int[] arr) {
      int[] answer = arr;
      for(int i = 0; i < n-1; i++){
          for(int j = 0; j < n-i-1; j++){
              if(arr[j] > arr[j+1]){
                  int tmp = arr[j];
                  arr[j] = arr[j+1];
                  arr[j+1] = tmp;
              }
          }
       }
       return answer;
    }

삽입 정렬

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

시간복잡도는 선택정렬, 버블정렬과 같은 O(n^2)이지만,
최선의 상황에서는 K-1로 동작할 수 있다.최악의 경우에도 선택정렬과 같은 시행회수인 n(n-1)/2이다.
따라서 선택, 버블정렬보다 보통 빠르게 동작한다.

✏️ 문제

* 설명
N개이 숫자가 입력되면 오름차순으로 정렬하여 출력하는 프로그램을 작성하세요.
정렬하는 방법은 삽입정렬입니다.


* 입력
첫 번째 줄에 자연수 N(1<=N<=100)이 주어집니다.
두 번째 줄에 N개의 자연수가 공백을 사이에 두고 입력됩니다. 각 자연수는 정수형 범위 안에 있습니다.

* 출력
오름차순으로 정렬된 수열을 출력합니다.

🔍풀이

비교 원소보다 크면 한칸씩 뒤로 계속 밀어주며 작거나 같으면 멈추고, 멈춘자리 뒤에 비교 원소를 넣어준다.

  public int[] solution(int n, int[] arr) {
      int[] answer = arr;
      for(int i = 1; i < n; i++){
      	int tmp = arr[i], j; //멈춘 자리를 찾기 위해 j를 미리 선언
          for(j = i-1; j >= 0 ; j--){
			if(arr[j] > tmp) arr[j+1] = arr[j]; //한칸씩 밀어주기
            else break; // 같거나 작은 수를 만나면 j값만 남기고 멈춤          
          }
          arr[j+1] = tmp; //for문 밖에서 선언된 j를 이용.
       }
       return answer;
    }