스트랜드 정렬

Strand sort
스트랜드 정렬 애니메이션

Strand sort는 목록 항목을 증가 순서로 정렬하는 재귀 정렬 알고리즘이다.입력 목록을 역순으로 정렬할 때 발생하는 O(n2) 최악의 시간 복잡성을 가지고 있다.[1]입력이 이미 소트된 목록일 때 발생하는 O(n)의 최상의 사례 시간 복잡성을 가지고 있다.[2]Strand sort는 공간의 복잡성이 O(n)이기 때문에 제자리에 있지 않다.[1]

알고리즘은 먼저 목록의 첫 번째 요소를 하위 목록으로 이동시킨다.[1]그런 다음 하위 목록의 마지막 요소를 원본 목록의 각 후속 요소와 비교한다.[1]원래 목록에 하위 목록의 마지막 요소보다 큰 요소가 있으면 해당 요소가 원래 목록에서 제거되고 하위 목록에 추가된다.[1]이 과정은 하위 목록의 마지막 요소를 원래 목록의 나머지 요소와 비교할 때까지 계속된다.[1]그런 다음 하위 목록이 새 목록으로 병합된다.[1]이 프로세스를 반복하고 모든 요소가 정렬될 때까지 모든 하위 목록을 병합하십시오.[1]이 알고리즘을 Strand sort라고 하는데, 이는 정렬되지 않은 요소들 안에서 한 번에 하나씩 제거되는 가닥이 있기 때문이다.[1]이 알고리즘은 또한 40개 미만의 요소에 대해서도 J Sort에서 사용된다.[3]

예.

이 예는 책, IT Enabled Practice 및 Emerging Management Paradigms에서 제공하는 알고리즘에 대한 설명을 기반으로 한다.[1]

1단계: 숫자 목록으로 시작: {5, 1, 4, 2, 0, 9, 6, 3, 8, 7 }

2단계: 목록의 첫 번째 요소를 새 하위 목록으로 이동: 하위 목록에 {5} 포함

3단계: 그런 다음 원래 목록을 반복하고 각 숫자를 5보다 큰 숫자가 나올 때까지 5와 비교하십시오.

  • 1 < 5 따라서 1은 하위 목록에 추가되지 않는다.
  • 4 < 5 so 4는 하위 목록에 추가되지 않는다.
  • 2 < 5 so 2는 하위 목록에 추가되지 않는다.
  • 0 < 5 따라서 0은 하위 목록에 추가되지 않는다.
  • 9 > 5 so 9가 하위 목록에 추가되고 원래의 목록에서 제거된다.

4단계: 이제 9보다 큰 숫자가 나올 때까지 원래 목록의 나머지 요소와 9를 비교하십시오.

  • 6 < 9 so 6은 하위 목록에 추가되지 않는다.
  • 3 < 9 so 3은 하위 목록에 추가되지 않는다.
  • 8 < 9 so 8은 하위 목록에 추가되지 않는다.
  • 7 < 9 so 7은 하위 목록에 추가되지 않는다.

5단계: 이제 9를 비교할 요소는 더 이상 없으므로 하위 목록을 솔루션 목록이라는 새로운 목록으로 병합하십시오.

5단계 후 원래 목록은 {1, 4, 2, 0, 6, 3, 8, 7}을(를) 포함한다.

하위 목록이 비어 있고 솔루션 목록에 {5, 9}이(가) 포함되어 있음

6단계: 원본 목록의 첫 번째 요소를 하위 목록으로 이동: 하위 목록에 {1} 포함

7단계: 원래 목록을 반복하고 1보다 큰 숫자가 나올 때까지 각 숫자를 1과 비교하십시오.

  • 4 > 1 그래서 4는 하위 목록에 추가되고 4는 원래 목록에서 삭제된다.

8단계: 이제 4보다 큰 숫자가 나올 때까지 원래 목록의 나머지 요소와 4를 비교하십시오.

  • 2 < 4 so 2는 하위 목록에 추가되지 않는다.
  • 0 < 4 따라서 0은 하위 목록에 추가되지 않는다.
  • 6 > 4 so 6이 하위 목록에 추가되고 원래의 목록에서 제거된다.

9단계: 이제 6보다 큰 숫자가 나올 때까지 원래 목록의 나머지 요소와 6을 비교하십시오.

  • 3 < 6 so 3은 하위 목록에 추가되지 않는다.
  • 8 > 6 so 8이 하위 목록에 추가되어 원래의 목록에서 제거된다.

10단계: 이제 8보다 큰 숫자가 나올 때까지 원래 목록의 나머지 요소와 8을 비교하십시오.

  • 7 < 8 so 7은 하위 목록에 추가되지 않는다.

11단계: 원본 목록에 {8}을(를) 비교할 요소가 더 이상 없으므로 하위 목록이 솔루션 목록과 병합됨이제 원래 목록에는 {2, 0, 3, 7}이(가) 포함되어 있고 하위 목록은 비어 있으며 솔루션 목록에는 {1, 4, 5, 6, 8, 9}이(가) 포함되어 있다.

12단계: 원본 목록의 첫 번째 요소를 하위 목록으로 이동하십시오.하위 목록에 {2} 포함

13단계: 원래 목록을 반복하고 2보다 큰 숫자가 나올 때까지 각 숫자를 2와 비교하십시오.

  • 0 < 2 따라서 0은 하위 목록에 추가되지 않는다.
  • 3 > 2 so 3이 하위 목록에 추가되어 원래의 목록에서 제거된다.

14단계: 이제 3보다 큰 숫자가 나올 때까지 3을 원래 목록의 나머지 요소와 비교하십시오.

  • 7 > 3 so 7이 하위 목록에 추가되어 원래의 목록에서 제거된다.

15단계: 원본 목록에 {7}을(를) 비교할 요소가 더 이상 없으므로 하위 목록이 솔루션 목록과 병합됨원래 목록에는 이제 {0}이(가) 포함되고 하위 목록은 비어 있으며 솔루션 목록에는 {1, 2, 3, 4, 5, 6, 7, 8, 9}이(가) 포함되어 있다.

16단계: 원본 목록의 첫 번째 요소를 하위 목록으로 이동하십시오.하위 목록에 {0}이(가) 포함되어 있음.

17단계: 원래 목록이 현재 비어 있으므로 하위 목록이 솔루션 목록과 병합됨현재 솔루션 목록에는 다음과 같은 {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}이(가) 포함되어 있다.이제 원래의 리스트에는 더 이상의 요소가 없고, 솔루션 리스트의 모든 요소들은 증가하는 숫자의 순서로 성공적으로 정렬되었다.

실행

Strand Sort는 삽입과 삭제가 많이 필요하므로 알고리즘 구현 시 링크된 목록을 사용하는 것이 가장 좋다.[2]링크된 목록은 반복기를 사용한 요소의 삽입과 제거에 대해 일정한 시간이 필요하다.링크된 목록을 통과하는 시간은 목록의 입력 크기와 직접 관련이 있다.[4]다음의 구현은 Java 8에서 수행되며, 책, IT Enabled Practice 및 Emerging Management Paradigms에서 나온 알고리즘에 대한 설명을 바탕으로 한다.[1]

꾸러미 스트랜드소트;  수입하다 java.util.*;  공중의 계급 스트랜드소트 {  정태의 LinkedList<정수> 솔리스트 = 새로운 LinkedList<정수>();  정태의 인트로 k = 0;   /** * 재귀 Strand Sort 메소드 입니다.의 링크된 리스트를 가지고 있다. * 정수(intersumer)를 매개변수로 사용한다.먼저 베이스 케이스를 점검해, 이 케이스가 어떻게 되어 있는지 확인한다. * 연결된 목록이 비어 있음그런 다음 Strand 정렬 알고리즘으로 이동하여 * 연결된 목록이 비어 있음 * * @param originList: * 연결된 정수 목록 */  공중의 정태의 공허하게 하다 StrandSortIterative(LinkedList<정수> 오리지널리스트) {    // 베이스 케이스   만일 (오리지널리스트.비어 있음()) {    돌아오다;   }    다른 {    // 하위 목록을 만들고 의 첫 번째 요소를 추가하십시오.    // 하위 목록에 연결된 원래 목록.    // 그런 다음 첫 번째 요소를 원래 목록에서 제거하십시오.    LinkedList<정수> 하위 목록 = 새로운 LinkedList<정수>();    하위 목록.덧셈을(오리지널리스트.우선하다());    오리지널리스트.먼저 제거();     // 원본 목록을 반복하여 요소가 있는지 확인하십시오.    // 하위 목록의 요소보다 큼    인트로 색인을 달다 = 0;    을 위해 (인트로 j = 0; j < 오리지널리스트.사이즈를 맞추다(); j++) {     만일 (오리지널리스트.얻다(j) > 하위 목록.얻다(색인을 달다)) {      하위 목록.덧셈을(오리지널리스트.얻다(j));      오리지널리스트.제거하다(j);      j = j - 1;      색인을 달다 = 색인을 달다 + 1;     }    }    // 솔루션 목록에 하위 목록을 병합하십시오.    // 이 단계에는 두 가지 사례가 있다.    // 사례 1: 첫 번째 재귀 호출, 모든 요소를 에 추가    // 솔루션 리스트(순차순    만일 (k == 0) {     을 위해 (인트로 i = 0; i < 하위 목록.사이즈를 맞추다(); i++) {       솔리스트.덧셈을(하위 목록.얻다(i));      k = k + 1;     }     }     // 사례 2: 첫 번째 재귀 호출 후    // 하위 목록을 솔루션 목록과 병합.    // 이것은 하위 목록에서 가장 큰 요소(항상 마지막 요소)를 비교함으로써 작동한다.    // 솔루션 목록의 첫 번째 요소.     다른 {     인트로 서브엔드 = 하위 목록.사이즈를 맞추다() - 1;     인트로 solStart = 0;     하는 동안에 (!하위 목록.비어 있음()) {       만일 (하위 목록.얻다(서브엔드) > 솔리스트.얻다(solStart)) {       solStart++;       } 다른 {       솔리스트.덧셈을(solStart, 하위 목록.얻다(서브엔드));       하위 목록.제거하다(서브엔드);       서브엔드--;       solStart = 0;      }      }     }     StrandSortIterative(오리지널리스트);   }   }   공중의 정태의 공허하게 하다 본래의(끈[] 아그) {   // 새 링크된 Integer 목록 만들기   LinkedList<정수> 오리지널리스트 = 새로운 LinkedList<정수>();    // 연결된 목록에 다음 정수 추가: {5, 1, 4, 2, 0, 9, 6, 3, 8, 7}    오리지널리스트.덧셈을(5);   오리지널리스트.덧셈을(1);   오리지널리스트.덧셈을(4);   오리지널리스트.덧셈을(2);   오리지널리스트.덧셈을(0);   오리지널리스트.덧셈을(9);   오리지널리스트.덧셈을(6);   오리지널리스트.덧셈을(3);   오리지널리스트.덧셈을(8);   오리지널리스트.덧셈을(7);    StrandSortIterative(오리지널리스트);   // 솔루션 목록 출력   을 위해 (인트로 i = 0; i < 솔리스트.사이즈를 맞추다(); i++) {    시스템.밖으로.인쇄하다(솔리스트.얻다(i));   }   }  }

참조

  1. ^ a b c d e f g h i j k IT enabled practices and emerging management paradigms. Gupta, I. C. (Ishwar Chandra), 1946-, Jaroliya, Deepak., Prestige Institute of Management and Research. (1st ed.). Indore: Prestige Institute of Management and Research. 2008. ISBN 9788174466761. OCLC 641462443.{{cite book}}: CS1 maint : 기타(링크)
  2. ^ a b "strand sort". xlinux.nist.gov. Retrieved 2018-11-06.
  3. ^ Sudipta., Mukherjee (2008). Data structures using C : 1000 problems and solutions. New Delhi: Tata McGraw-Hill. ISBN 9780070667655. OCLC 311311576.
  4. ^ "LinkedLists". www.cs.cmu.edu. Retrieved 2018-11-06.