arrays - 자바스크립트 - 숫자 문자 정렬



정렬:3 가지 종류의 숫자를 포함하는 배열을 정렬하는 방법 (10)

@ElYusubov를 기반으로하는 그루비 솔루션이 있지만 버킷 (5)을 시작 및 버킷 (15)으로 푸시하는 대신 끝냅니다. 5가 시작쪽으로 이동하고 15가 끝쪽으로 이동하도록 선별기를 사용하십시오.

버킷을 끝에서 현재 위치로 바꿀 때마다 끝이 감소합니다. 요소를 다시 확인해야하므로 현재 카운터를 증가시키지 마십시오.

array = [15,5,10,5,10,10,15,5,15,10,5]

    def swapBucket(int a, int b) {

        if (a == b) return; 
        array[a] = array[a] + array[b]
        array[b] = array[a] - array[b]
        array[a] = array[a] - array[b]

    }

def getBucketValue(int a) {
    return array[a];
}

def start = 0, end = array.size() -1, counter = 0;
// we can probably do away with this start,end but it helps when already sorted.

// start - first bucket from left which is not 5
while (start < end) {

    if (getBucketValue(start) != 5) break;
    start++;

}     

// end - first bucket from right whichis not 15
while (end > start) {

    if (getBucketValue(end) != 15) break;
    end--;

}

// already sorted when end = 1 { 1...size-1 are Buck(15) } or start = end-1      

for (counter = start; counter < end;) {

    def value = getBucketValue(counter)

    if (value == 5) { swapBucket(start, counter); start++; counter++;}
    else if (value == 15) { swapBucket(end, counter); end--; } // do not inc counter
    else { counter++; }

}

for (key in array) { print " ${key} " }

예를 들면 다음과 같습니다. int A[] = {3,2,1,2,3,2,1,3,1,2,3};

배열을 효율적으로 정렬하는 방법?

이것은 면접을위한 것입니다. 의사 코드가 필요합니다.


Answer #1

robert가 basketsort (또는 bucketsort)가이 상황에서 최고라고 언급했듯이.

나는 또한 다음 알고리즘을 추가 할 것이다 (사실 busket 정렬과 매우 비슷하다).

[의사 코드는 자바 스타일입니다]

HashMap<Integer, Interger> map 만들고 배열을 순환합니다.

for (Integer i: array)
{
    Integer value = map.get(i);
    if (value == null)
    {
        map.put(i, 1);
    }
    else
    {
        map.put(i, value+1);
    }
}

Answer #2

그것을 정렬하는 유망한 방법은 계산 방식 인 것 같습니다. 리처드 버클 랜드 (Richard Buckland)의 강의 ( 15:20 부분)를 살펴볼 가치가 있습니다.

마찬가지로 카운팅 정렬과 비슷하지만 도메인을 나타내는 배열을 만들고, 모든 요소를 ​​0으로 초기화 한 다음 배열을 반복하고 이러한 값을 계산하는 것이 더 좋습니다. 도메인 값의 개수를 알면 그에 따라 배열의 값을 다시 쓸 수 있습니다. 그러한 알고리즘의 복잡도는 O (n)입니다.

C ++ 코드는 내가 설명한대로 동작합니다. 그 복잡성은 실제로 O (2n)이지만 :

int A[] = {3,2,1,2,3,2,1,3,1,2,3};
int domain[4] = {0};

// count occurrences of domain values - O(n):  
int size = sizeof(A) / sizeof(int);
for (int i = 0; i < size; ++i)
    domain[A[i]]++;

// rewrite values of the array A accordingly - O(n):    
for (int k = 0, i = 1; i < 4; ++i)
    for (int j = 0; j < domain[i]; ++j)
        A[k++] = i;

도메인 값 사이에 큰 차이가있는 경우 도메인을 배열로 저장하는 것이 비효율적이라는 점에 유의하십시오. 이 경우 맵을 사용하는 것이 훨씬 더 좋은 생각입니다. (그것을 지적하기 위해 abhinav 에게 감사드립니다). 다음은 도메인 값을 저장하기 위해 std::map 을 사용하는 C ++ 코드입니다 - 발생 개수 쌍 :

int A[] = {2000,10000,7,10000,10000,2000,10000,7,7,10000};
std::map<int, int> domain;

// count occurrences of domain values:  
int size = sizeof(A) / sizeof(int);
for (int i = 0; i < size; ++i)
{
    std::map<int, int>::iterator keyItr = domain.lower_bound(A[i]);
    if (keyItr != domain.end() && !domain.key_comp()(A[i], keyItr->first))
        keyItr->second++; // next occurrence 
    else
        domain.insert(keyItr, std::pair<int,int>(A[i],1)); // first occurrence
}

// rewrite values of the array A accordingly:    
int k = 0;
for (auto i = domain.begin(); i != domain.end(); ++i)
    for (int j = 0; j < i->second; ++j)
        A[k++] = i->first;

(만약 위의 코드에서 std::map 을 더 효율적으로 사용하는 방법이 있다면 알려주세요)



Answer #4

나는 당신이 물통 종류 를 사용하려고하는 질문이라고 생각합니다. 작은 수의 값이있는 경우 버킷 정렬은 일반적으로 사용되는 quicksort 또는 mergesort보다 훨씬 빠릅니다.


Answer #5

문제 설명 : 당신은 n 개의 버킷이 있고, 각 버켓에는 하나의 동전이 들어 있으며, 동전의 값은 5 또는 10 또는 20이 될 수 있습니다.이 제한 하에서 버킷을 정렬해야합니다 : 1.이 2 개의 함수 만 사용할 수 있습니다 : SwitchBaskets (Basket1 , Basket2) - 2 개 바구니 바꿔 치기 GetCoinValue (Basket1) - 선택한 바구니에 동전 값 반환 2. 크기 배열을 정의 할 수 없음 n. 가능한 한 스위치 기능을 사용하지 마십시오.

내 단순한 의사 코드 솔루션으로 O (n) 복잡성이있는 언어로 구현할 수 있습니다.

나는 바구니에서 동전을 뽑을 것이다 1) 만약 그것이 5라면 - 처음으로 밀어 넣는다, 2) 20- 마지막으로 밀어 넣는다, 3) 10이면 - 그대로 둔다. 4) 다음 줄에있는 양동이를 살펴보십시오.

편집 : 첫 번째 또는 마지막 위치요소를 푸시 할 수 없으면 sorting 이 이상적으로 구현에 적합합니다. 작동 방식은 다음과 같습니다.

Merge sort는 이미 정렬 된 목록을 새 정렬 된 목록으로 쉽게 병합 할 수 있다는 장점을 이용합니다. 그것은 두 개의 요소 (즉, 1을 2로, 3을 4로 ...)를 비교하고 첫 번째가 두 번째 요소 다음에 오는 경우이를 서로 바꿔서 시작합니다. 그런 다음 두 결과 목록 각각을 4 목록으로 병합 한 다음 4 목록을 병합합니다. 마지막 두 개의 목록이 최종 정렬 목록에 병합 될 때까지 여기에 설명 된 알고리즘 중 최악의 실행 시간이 O (n log n)이기 때문에 아주 큰 목록으로 확장하는 것이 가장 좋습니다. Merge 정렬은 프로그래밍 언어의 표준 정렬 루틴에 사용되는 비교적 최근의 실제 구현에 대한 인기가 급증한 것을 보았습니다


Answer #6

우리는 두 개의 숫자가 배열 된 문제를 풀 수 있습니다. [1,2,1,2,2,2,1,1]

우리는 minm 스왑을 사용하여 한 번에 o (n)을 정렬 할 수 있습니다. 서로 만날 때까지 왼쪽과 오른쪽에서 두 개의 포인터를 시작합니다. 왼쪽 요소가 더 큰 경우 왼쪽 요소를 오른쪽으로 바꿉니다. (오름차순 정렬)

우리는 3 개의 숫자 (k-1 패스)에 대해 또 다른 패스를 할 수 있습니다. 패스 1에서 우리는 1을 그들의 최종 포지션으로 이동 시켰고 패스 2에서 2를 움직였다.

def start = 0, end = array.size() - 1;

// Pass 1, move lowest order element (1) to their final position 
while (start < end) {
    // first element from left which is not 1
    for ( ; Array[start] ==  1 && start < end ; start++);
    // first element from right which IS 1
    for ( ; Array[end] != 1 && start < end ; end--);

    if (start < end) swap(start, end);
}     

// In second pass we can do 10,15

// We can extend this using recurion, for sorting domain = k, we need k-1 recurions 


Answer #8

재미를 위해서 ElYusubub가 제안한 것처럼 "가치를 최우선으로 푸는"방법을 구현하는 방법은 다음과 같습니다.

sort(array) {
  a = 0
  b = array.length
  # a is the first item which isn't a 1 
  while array[a] == 1
    a++
  # b is the last item which isn't a 3
  while array[b] == 3
    b--

  # go over all the items from the first non-1 to the last non-3
  for (i = a; i <= b; i++)
    # the while loop is because the swap could result in a 3 or a 1
    while array[i] != 2
      if array[i] == 1
        swap(i, a)
        while array[a] == 1
          a++
      else # array[i] == 3
        swap(i, b)
        while array[b] == 3
          b--

이것은 실제로 최적의 솔루션이 될 수 있습니다. 나는 잘 모르겠다.


Answer #9
//Bubble sort for unsorted array - algorithm
public void  bubleSort(int arr[], int n) { //n is the length of an array
    int temp;
    for(int i = 0; i <= n-2; i++){
        for(int j = 0; j <= (n-2-i); j++){
            if(arr[j] > arr[j +1]){
                temp = arr[j];
                arr[j] = arr[j +1];
                arr[j + 1] = temp;

            }
        }

    }




pseudocode