41강 컬렉션 프레임 웍 연습2 / 정렬(sort)

알고리즘 
       : 문제를 해결하기 위한 절차적 해결 과정
정렬 알고리즘
       : 데이터를 순서대로 나열하기 위한 절차적인 과정
정렬 알고리즘의 종류
       1. 선택 정렬(Selection Sort)
       2. 삽입 정렬(Insertion Sort)
       3. 버블 정렬(Bubble Sort)
41-1 ) 선택 정렬
       : 최소값 혹은 최대값을 선택해서 가장 앞에다가 위치하여
         선택할 위치를 이동하며 정렬하는 방법

       장점 : 구현하기 쉽다.
       단점 : 다른 정렬에 비해 시간이 오래 걸린다.

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

              2) 가장 작은 값을 찾으면 그 값을 현재 인덱스의 값과 바꿔준다.
                     ar[min] <-> ar[i]
              3) 다음 인덱스로 이동하여 위 과정을 반복한다.

       시간 복잡도
              O(n²)

            

              1) min : 0, j : 1
                     만약 ar[0] > ar[1]이라면, ar[0] <-> ar[1] ↓

              2) min : 0, j : 2
                     만약 ar[0] > ar[2]이라면, ar[0] <-> ar[2] 변경 X↓

              1) min : 1, j : 2
                     만약 ar[1] > ar[2]이라면, ar[1] <-> ar[2] ↓

              2) min : 1, j : 3
                     만약 ar[1] > ar[3]이라면, ar[1] <-> ar[3] 변경 X↓

 

 

              1) min : 2, j : 3
                     만약 ar[2] > ar[3]이라면, ar[2] <-> ar[3] ↓

              2) min : 2, j : 4
                     만약 ar[2] > ar[4]이라면, ar[2] <-> ar[4] ↓

              3) min : 2, j : 5
                     만약 ar[2] > ar[5]이라면, ar[2] <-> ar[5] ↓

              4) min : 2, j : 6
                     만약 ar[2] > ar[6]이라면, ar[2] <-> ar[6] 변경 X↓

 

              1) min : 3, j :4
                     만약 ar3] > ar[4]이라면, ar[3] <-> ar[4] ↓

               <실습>SelectionSort

                i : 최소값을 위치시킬 가장 앞에 있는 idx
                i의 범위 : 0 ~ 마지막 idx - 1
                j : 맨 앞에 있는 idx(i)와 비교할 idx
                j의 범위 : i+1 ~ 마지막 idx

 

41-2 ) 삽입 정렬
       : 지정한 값의 삽입할 위치를 찾아 정렬하는 방법

 

       기본 로직
       1) 삽입정렬은 두번째 idx(현재 위치 : i, 비교위치 : j)부터 시작
              i = 1
       2) 현재 idx는 별도의 변수에 저장
              idx = i
       3) 비교 idx = 현재 idx - 1
              j = i - 1
       4) idx값 < 비교idx의 값 : 
              idx <-> j
              idx = j
       * idx랑 j값을 바꾸므로, 현재 idx의 값으로 계속 비교해줘야 함
       5) idx > 비교idx의 값 : 비교idx--

       <실습>InsertionSort

       i : 위치를 찾을 idx
       -> 범위 : 1 ~ 배열의 끝
       j : 비교할 idx
       -> 범위 : i-1 ~ 0까지
       
       만약, 현재 값 < 비교 idx 라면,
       값을 바꾸고, idx를 j로 변경

 

41-3 ) 버블 정렬
       : 인접한 두 수를 비교해서 큰 수를 뒤로 보내는 알고리즘
         정렬과정이 거품이 일어나는 것과 비슷하다 하여 버블!

       장점 : 구현이 쉽고 코드가 직관적이다.
       단점 : 시간이 오래 걸린다.
                최선, 최악, 평균 모두 O(n²)이라는 시간 복잡도를 가진다.

       기본 로직

       <실습>BubbleSort

       i : 제일 큰 값이 올 위치
       -> 범위 : 배열 끝 ~ 0
       j : 비교할 idx
       -> 범위 : 0 ~ i까지