정렬된 배열 "sorted"를 정렬하기.

1. 크기 n의 배열이 주어진다고 가정합니다.


2. 반복 i에서 새로운 난수 값이 주어지고, 배열의 끝에 삽입됩니다.


3. 배열은 다시 정렬되고, 가장 작은 값의 항목은 삭제됩니다.


4. n번의 반복 후, 유지된 배열에는 가장 큰 값의 항목이 포함됩니다.

예를 들어, Java 구문으로는 다음과 같을 것입니다:

List l = new ArrayList();
l.add(new Integer(2));
l.add(new Integer(3));
l.add(new Integer(6));
l.add(new Integer(9));
Random rand = new Random();
for (int i=0; i < n; i++) {
  l.add(new Integer(rand.nextInt(1000)));
}    
Collections.sort(l);
l.remove(0);

하지만 효율적이지 않은 것 같습니다. 더 나은 알고리즘이 있을까요?

답변 1

이 값에 대한 이진 삽입 (이진 검색처럼 작동)을 사용하십시오. 가장 작은 값을 버립니다. 매우 빠릅니다.

그런데 - 이것은 편리한 확장 메서드로 구현 될 수 있습니다:

private static int GetSortedIndex(this IList list, IComparer comparer, object item, int startIndex, int endIndex)
{
  if (startIndex > endIndex)
  {
    return startIndex;
  }
  var midIndex = startIndex + (endIndex - startIndex) / 2;
  return comparer.Compare(list[midIndex], item) < 0 ?
    GetSortedIndex(list, comparer, item, midIndex + 1, endIndex) :
    GetSortedIndex(list, comparer, item, startIndex, midIndex - 1);
}
public static void InsertSorted(this IList list, IComparer comparer, object item)
{
  list.Insert(list.GetSortedIndex(comparer, item), item);
}

자바 equivalent

public static void main(String[] args)
{
   List l = new ArrayList();
   l.add(new Integer(2));
   l.add(new Integer(3));
   l.add(new Integer(6));
   l.add(new Integer(9));
   Random rand = new Random();
   for (int i=0; i < 10; i++) {
       Integer rnd = new Integer(rand.nextInt(1000));
       int pos = Collections.binarySearch(l,rnd);
       if(pos < 0) pos = ~pos;
       l.add(pos,rnd);
   }    
   System.out.println(l);
}

public static void main(String[] args)
{
   List l = new ArrayList();
   l.add(new Integer(2));
   l.add(new Integer(3));
   l.add(new Integer(6));
   l.add(new Integer(9));
   Random rand = new Random();
   for (int i=0; i < 10; i++) {
       Integer rnd = new Integer(rand.nextInt(1000));
       int pos = Collections.binarySearch(l,rnd);
       if(pos < 0) pos = ~pos;
       l.add(pos,rnd);
   }    
   System.out.println(l);
}

public static void main(String[] args)
{
   List l = new ArrayList();
   l.add(new Integer(2));
   l.add(new Integer(3));
   l.add(new Integer(6));
   l.add(new Integer(9));
   Random rand = new Random();
   for (int i=0; i < 10; i++) {
       Integer rnd = new Integer(rand.nextInt(1000));
       int pos = Collections.binarySearch(l,rnd);
       if(pos < 0) pos = ~pos;
       l.add(pos,rnd);
   }    
   System.out.println(l);
}

public static void main(String[] args)
{
   List l = new ArrayList();
   l.add(new Integer(2));
   l.add(new Integer(3));
   l.add(new Integer(6));
   l.add(new Integer(9));
   Random rand = new Random();
   for (int i=0; i < 10; i++) {
       Integer rnd = new Integer(rand.nextInt(1000));
       int pos = Collections.binarySearch(l,rnd);
       if(pos < 0) pos = ~pos;
       l.add(pos,rnd);
   }    
   System.out.println(l);
}

답변 2

정렬된 배열의 정렬 과정
배열은 프로그래밍에서 자주 사용되는 데이터 구조로, 데이터를 효율적이고 조직적으로 저장하는 데 사용됩니다. 이러한 배열은 종종 정렬된 상태로 유지되며, 이는 데이터를 빨리 찾을 수 있도록 도와줍니다. 그러나 때로는 변동적인 데이터 입력 또는 분석 과정에 의해 배열이 고려하지 않은 순서로 변경될 수 있습니다. 이럴 때, 우리는 '정렬된' 배열을 다시 정렬해야 합니다.
정렬된 배열의 재정렬 과정은 주어진 데이터 요소를 올바른 순서로 재배열하는 작업입니다. 이렇게 하면 데이터에 대한 빠른 액세스와 처리가 가능해지며, 프로그램의 성능을 향상시키는 데 도움이 됩니다. 이를 위해 여러 정렬 알고리즘이 개발되어 왔으며, 각각은 고유한 특성과 사용 사례를 가지고 있습니다.
가장 널리 사용되는 정렬 알고리즘 중 하나는 '버블 정렬'입니다. 이 알고리즘은 인접한 두 요소를 비교하고 필요한 경우 교환하는 과정을 반복하여 배열을 정렬합니다. 버블 정렬은 구현이 간단하고 이해하기 쉬우며, 작은 크기의 배열에서는 효과적이지만, 큰 크기의 배열에서는 비효율적일 수 있습니다.
또 다른 널리 사용되는 정렬 알고리즘은 '삽입 정렬'입니다. 이 알고리즘은 배열을 정렬 완료된 부분과 정렬되지 않은 부분으로 분리하고, 정렬되지 않은 요소를 기존의 정렬된 부분에 삽입하는 과정을 반복하여 배열을 정렬합니다. 삽입 정렬은 버블 정렬에 비해 약간 더 효율적이며, 부분적으로 정렬되어 있는 배열에 대해서는 더욱 우수한 성능을 보입니다.
대용량 데이터를 다루는 데는 '병합 정렬'이라는 알고리즘을 사용하는 것이 효과적입니다. 이 알고리즘은 배열을 분할하여 각각을 정렬한 후 병합하는 과정을 반복하여 최종적으로 정렬된 배열을 만듭니다. 병합 정렬은 안정적인 정렬 알고리즘으로, 데이터 분할 및 병합 단계에서 효율적으로 동작합니다.
정렬된 배열을 재정렬하는 과정에서는 알고리즘의 성능, 알고리즘의 구현 난이도, 데이터 크기 등을 고려해야 합니다. 데이터의 유형과 크기에 따라 적합한 알고리즘을 선택하고, 구현하기 전에 해당 알고리즘의 특징과 동작 방식을 이해하는 것이 중요합니다.
이처럼 정렬된 배열의 재정렬은 프로그래밍에서 중요한 작업 중 하나입니다. 올바른 알고리즘 선택과 구현을 통해 데이터 처리의 효율성을 극대화할 수 있으며, 향후 프로그램의 성능 향상에 기여할 수 있습니다.