[자료구조] Java 삽입정렬 (insertion sort) 정리

Java 삽입정렬 (insertion sort) 정리

삽입 정렬(insertion sort) 알고리즘은 반복적으로 특정 값을 이미 정렬된 목록의 부분 집합에 삽입함으로써 값들의 목록을 정렬한다.

한번에 하나씩 정렬되지 않은 원소는 정렬된 부분 집합의 적절한 위치에 삽입된다. 이러한 과정은 전체 목록이 정렬될 때까지 계속된다.

① 단지 한 개의 값만을 포함하는 정렬된 목록으로 시작한다.

② 목록의 처음 두 개의 값을 비교하고, 필요하면 이들을 교환함으로써 정렬한다.

③ 목록의 세 번째 값을 이미 정렬된 처음 두 개의 값과 비교하여 적절한 위치에 삽입한다.

④ 다음에 네 번째 값을 목록의 처음 세 개의 값과 비교하여 적절한 위치에 삽입한다.

⑤ 삽입이 이루어질때마다 정렬된 부분 집합에 속한 값들의 개수는 하나씩 증가한다.

⑥ 이러한 과정을 목록에 포함된 모든값들이 적절한 위치에 삽입될 때까지 계속한다.

삽입 과정은 삽입되는 원소에 대한 공간을 마련하기 위해서 목록에 포함된 다른 값들에 대한 이동을 요구한다.

* 삽입 정렬 소스코드

public class Sorting {          public static void insertionSort(Comparable[] list){                  // 정렬 비교대상 index 1 부터 루프를 돌면서 비교 삽입 정렬한다.         for(int index = 1; index < list.length; index++){                          Comparable key = list[index];             int position = index;                          // 정렬 부분집합의 뒤의 값부터 index 값을 비교하면서              // index 값보다 작은 값이 나올때까지 밀어내고 적절한 위치에 삽입한다.             while(position >0 && key.compareTo(list[position-1])<0){                                  list[position] = list[position-1];                 position--;             }                          list[position] = key;         }     } }

선택 정렬의 구현과 유사하게 insertionSort 메소드는 두 개의 루프를 사용하여 배열을 정렬한다. 그러나 삽입 정렬에서는 바깥 루프는 삽입된 다음 값에 대한 배열의 인덱스를 제어한다.

안쪽 루프는 삽입될 값을 그 왼쪽에 위치한 값들(전체 목록의 정렬된 부분 집합)과 비교한다.

현재의 삽입 값이 position에 위치한 값보다 작으면, position에 위치한 값을 오른쪽으로 이동시킨다.

이러한 이동은 삽입할 값을 위한 적절한 위치를 만날 때까지 계속 된다.

바깥 루프의 매번 반복은 목록 전체가 정렬될때까지 목록의 정렬된 부분 집합에 값을 한 개씩 추가한다.

[자료구조] Java 선택정렬 (Selection Sort) 정리

* 삽입 정렬 사용 예제

위의 삽입 정렬에서 정렬의 기준은 넘어온 Comparable 인터페이스를 구현한 배열의 compareTo 함수의 기준에 의존하고 있다. 

Comparable 인터페이스를 구현한 Contact 클래스를 만들어보았다.

public class Contact implements Comparable{                  private String firstName, lastName, phone;                  public Contact(String first, String last, String telephone){                          firstName = first;             lastName = last;             phone = telephone;                      }         // Comparable 인터페이스의 구현함수 compareTo         // 데이터를 비교하는 compareTo 함수를 구현한다.         @Override         public int compareTo(Object other) {                          int result;                          String otherFirst = ((Contact)other).getFirstName();             String otherLast = ((Contact)other).getLastName();                          // 비교 대상의 lastName이 같으면 firstName 비교             if(lastName.equals(otherLast))                 result = firstName.compareTo(otherFirst);             else    // lastName이 같지않으면 lastName으로 비교                 result = lastName.compareTo(otherLast);                          return result;         }                  // 이름 반환         public String getFirstName(){             return firstName;         }                  // 성 반환         public String getLastName(){             return lastName;         }                  // 두개의 객체의 성과 이름이 모두 일치하면 True         public boolean equals(Object other){             return (lastName.equals(((Contact)other).getLastName()) &&                     firstName.equals(((Contact)other).getFirstName()));         }                  public String toString(){             return lastName + ", " + firstName + "\t" + phone;         }              }

Contact 클래스는 고객의 "FirstName", "LastName", "telephone"를 받아 객체를 생성하며, compareTo 메소드는 "LastName"을 비교하고 "LastNmae"이 같으면 "FirstName"을 비교하여 결과를 반환한다.

이제 Contact 클래스를 배열로 생성하여 데이터를 넣은 후, 삽입 정렬 클래스를 사용하여 "LastName", "FirstName" 순으로 정렬해보자.

public class SortingTest {          public static void main(String[] args){                  Contact[] friends = new Contact[8];              friends[0] = new Contact("Steve", "Smith", "734-521-1214");         friends[1] = new Contact("Kelly", "Barnes", "165-132-5654");         friends[2] = new Contact("Make", "Ball", "223-323-2333");         friends[3] = new Contact("Mynsu", "Kang", "345-643-3113");         friends[4] = new Contact("Calm", "Jeremy", "564-323-1645");         friends[5] = new Contact("Jane", "Moon", "546-413-4543");         friends[6] = new Contact("Hyun", "Lee", "442-454-3211");         friends[7] = new Contact("Cream", "Jone", "751-231-5618");                           Sorting.insertionSort(friends);                  for(Contact friend : friends){             System.out.println(friend);         }     } }

Contact 배열을 생성하여, 데이터를 입력 후  insertionSort 를 이용하여 삽입정렬했다.

"LastName", "FirstName" 순서로 정렬된 것을 볼 수 있다.

insertionSort.zip

출처: https://hyeonstorage.tistory.com/268?category=578561 [개발이 하고 싶어요]