Рубрики

Сортировать n чисел в диапазоне от 0 до n ^ 2 — 1 за линейное время

Дан массив чисел размером n. Также дано, что элементы массива находятся в диапазоне от 0 до n 2 — 1. Сортировка данного массива по линейному времени.

Примеры:

Since there are 5 elements, the elements can be from 0 to 24.
Input: arr[] = {0, 23, 14, 12, 9}
Output: arr[] = {0, 9, 12, 14, 23}

Since there are 3 elements, the elements can be from 0 to 8.
Input: arr[] = {7, 0, 2}
Output: arr[] = {0, 2, 7}

Решение: Если мы используем Counting Sort , это займет O (n ^ 2) времени, так как данный диапазон имеет размер n ^ 2. Использование любой сортировки на основе сравнения, такой как Merge Sort , Heap Sort и т. Д., Заняло бы O (nLogn) время.
Теперь возникает вопрос, как это сделать в 0 (n)? Во-первых, возможно ли это? Можем ли мы использовать данные, указанные в вопросе? n чисел в диапазоне от 0 до n 2 — 1?
Идея заключается в использовании Radix Sort . Ниже приводится стандартный алгоритм сортировки по радиксу.

1) Do following for each digit i where i varies from least 
   significant digit to the most significant digit.
…………..a) Sort input array using counting sort (or any stable 
         sort) according to the i’th digit

Пусть во входных целых числах будет d цифр. Radix Sort занимает время O (d * (n + b)), где b является базой для представления чисел, например, для десятичной системы, b равно 10. Поскольку n 2 -1 является максимально возможным значением, значение d будет быть O (log b (n)). Таким образом, общая временная сложность составляет O ((n + b) * O (log b (n)). Это выглядит больше, чем временная сложность алгоритмов сортировки на основе сравнения для большого k. Идея состоит в том, чтобы изменить базу b. Если мы установим b как n, значение O (log b (n)) становится O (1), а общая сложность времени становится O (n).

arr[] = {0, 10, 13, 12, 7}

Let us consider the elements in base 5. For example 13 in
base 5 is 23, and 7 in base 5 is 12.
arr[] = {00(0), 20(10), 23(13), 22(12), 12(7)}

After first iteration (Sorting according to the last digit in 
base 5),  we get.
arr[] = {00(0), 20(10), 12(7), 22(12), 23(13)}

After second iteration, we get
arr[] = {00(0), 12(7), 20(10), 22(12), 23(13)}

Ниже приведена реализация для сортировки массива размером n, где элементы находятся в диапазоне от 0 до n 2 — 1.

C ++

#include<iostream>

using namespace std;

  
// Функция для подсчета сортировки arr [] в соответствии с
// цифра, представленная exp.

int countSort(int arr[], int n, int exp)

{

  

    int output[n]; // выходной массив

    int i, count[n] ;

    for (int i=0; i < n; i++)

       count[i] = 0;

  

    // Сохраняем количество вхождений в count []

    for (i = 0; i < n; i++)

        count[ (arr[i]/exp)%n ]++;

  

    // Изменить count [i] так, чтобы count [i] теперь содержал фактический

    // положение этой цифры в выходных данных []

    for (i = 1; i < n; i++)

        count[i] += count[i - 1];

  

    // Создаем выходной массив

    for (i = n - 1; i >= 0; i--)

    {

        output[count[ (arr[i]/exp)%n] - 1] = arr[i];

        count[(arr[i]/exp)%n]--;

    }

  

    // Копируем выходной массив в arr [], так что теперь arr []

    // содержит отсортированные номера по текущей цифре

    for (i = 0; i < n; i++)

        arr[i] = output[i];

}

  

  
// Основная функция для сортировки arr [] размера n с использованием Radix Sort

void sort(int arr[], int n)

{

    // Делаем подсчет сортировки по первой цифре в базе n. Обратите внимание, что

    // вместо передачи цифр передается exp (n ^ 0 = 1).

    countSort(arr, n, 1);

  

    // Делаем подсчет для сортировки второй цифры в базе n. Обратите внимание, что

    // вместо передачи цифр передается exp (n ^ 1 = n).

    countSort(arr, n, n);

}

  
// Вспомогательная функция для печати массива

void printArr(int arr[], int n)

{

    for (int i = 0; i < n; i++)

        cout << arr[i] << " ";

}

  
// Программа драйвера для проверки вышеуказанных функций

int main()

{

    // Поскольку размер массива равен 7, элементы должны быть от 0 до 48

    int arr[] = {40, 12, 45, 32, 33, 1, 22};

    int n = sizeof(arr)/sizeof(arr[0]);

    cout << "Given array is n";

    printArr(arr, n);

  

    sort(arr, n);

  

    cout << "nSorted array is n";

    printArr(arr, n);

    return 0;

}

Джава

// Java-программа для сортировки массива размером n, где элементы
// в диапазоне от 0 до n ^ 2 - 1.

class Sort1ToN2

{

    // Функция для подсчета сортировки arr [] в соответствии с

    // цифра, представленная exp.

    void countSort(int arr[], int n, int exp)

    {

        int output[] = new int[n]; // выходной массив

        int i, count[] = new int[n] ;

        for (i=0; i < n; i++)

           count[i] = 0;

  

        // Сохраняем количество вхождений в count []

        for (i = 0; i < n; i++)

            count[ (arr[i]/exp)%n ]++;

  

        // Изменить count [i] так, чтобы count [i] теперь содержал фактический

        // положение этой цифры в выходных данных []

        for (i = 1; i < n; i++)

            count[i] += count[i - 1];

  

        // Создаем выходной массив

        for (i = n - 1; i >= 0; i--)

        {

            output[count[ (arr[i]/exp)%n] - 1] = arr[i];

            count[(arr[i]/exp)%n]--;

        }

  

        // Копируем выходной массив в arr [], так что теперь arr []

        // содержит отсортированные номера по текущей цифре

        for (i = 0; i < n; i++)

            arr[i] = output[i];

    }

  

  

    // Основная функция для сортировки arr [] размера n с использованием Radix Sort

    void sort(int arr[], int n)

    {

        // Делаем подсчет сортировки по первой цифре в базе n. Обратите внимание, что

        // вместо передачи цифр передается exp (n ^ 0 = 1).

        countSort(arr, n, 1);

  

        // Делаем подсчет для сортировки второй цифры в базе n. Обратите внимание, что

        // вместо передачи цифр передается exp (n ^ 1 = n).

        countSort(arr, n, n);

    }

  

    // Вспомогательная функция для печати массива

    void printArr(int arr[], int n)

    {

        for (int i = 0; i < n; i++)

            System.out.print(arr[i]+" ");

    }

  

    // Программа драйвера для проверки вышеуказанных функций

    public static void main(String args[])

    {

        Sort1ToN2 ob = new Sort1ToN2();

  

        // Поскольку размер массива равен 7, элементы должны быть от 0 до 48

        int arr[] = {40, 12, 45, 32, 33, 1, 22};

        int n = arr.length;

        System.out.println("Given array");

        ob.printArr(arr, n);

  

        ob.sort(arr, n);

  

        System.out.println("Sorted array");

        ob.printArr(arr, n);

    }

}
/ * Этот код предоставлен Раджатом Мишрой * /

python3

# Python3 реализация для сортировки
# массив размера n

  
# Функция для подсчета рода arr []
# в соответствии с цифрой, представленной exp.

def countSort(arr, n, exp): 

    output = [0] * n # выходной массив

    count = [0] * n

    for i in range(n):

        count[i] = 0

  

    # Хранить количество вхождений в count []

    for i in range(n):

        count[ (arr[i] // exp) % n ] += 1

  

    # Измените count [i] так, чтобы count [i] теперь содержал

    # фактическая позиция этой цифры на выходе []

    for i in range(1, n): 

        count[i] += count[i - 1

  

    # Построить выходной массив

    for i in range(n - 1, -1, -1): 

  

        output[count[ (arr[i] // exp) % n] - 1] = arr[i] 

        count[(arr[i] // exp) % n] -= 1

  

    # Скопируйте выходной массив в arr [], чтобы

    # arr [] теперь содержит отсортированные числа в соответствии с

    # до текущей цифры

    for i in range(n): 

        arr[i] = output[i] 

  
# Основная функция для этого вида arr [] из
# размер n с использованием Radix Sort

def sort(arr, n) :

      

    # Делать подсчет сортировки по первой цифре в базе n.

    # Обратите внимание, что вместо передачи цифр,

    # exp (n ^ 0 = 1) пройдено.

    countSort(arr, n, 1

  

    # Делать подсчет сортировки для второй цифры в базе n.

    # Обратите внимание, что вместо передачи цифр,

    # exp (n ^ 1 = n) пройдено.

    countSort(arr, n, n) 

  
Код водителя

if __name__ =="__main__"

      

    # Так как размер массива равен 7, элементы должны

    # быть от 0 до 48

    arr = [40, 12, 45, 32, 33, 1, 22]

    n = len(arr) 

    print("Given array is")

    print(*arr)

      

    sort(arr, n)

      

    print("Sorted array is")

    print(*arr)

  
# Этот код предоставлен
# Шубхам Сингх (SHUBHAMSINGH10)

C #

// C # программа для сортировки массива
// размер n, где элементы
// в диапазоне от 0 до n ^ 2 - 1.

using System;

  

class GFG {

      

    // Функция для подсчета

    // сортировка arr [] согласно

    // цифра, представленная exp.

    static void countSort(int[] arr, 

                          int n, 

                          int exp)

    {

          

        // выходной массив

        int[] output = new int[n]; 

        int[] count = new int[n] ;

        int i;

        for (i = 0; i < n; i++)

        count[i] = 0;

  

        // Сохранить количество

        // вхождения в count []

        for (i = 0; i < n; i++)

            count[(arr[i] / exp) % n ]++;

  

        // Изменим count [i] так, чтобы

        // count [i] теперь содержит фактический

        // положение этой цифры в выходных данных []

        for (i = 1; i < n; i++)

            count[i] += count[i - 1];

  

        // Создаем выходной массив

        for (i = n - 1; i >= 0; i--)

        {

            output[count[(arr[i] / 

                   exp) % n] - 1] = arr[i];

            count[(arr[i] / exp) % n]--;

        }

  

        // Копируем выходной массив в

        // arr [], так что теперь arr []

        // содержит отсортированные номера

        // в соответствии с текущей цифрой

        for (i = 0; i < n; i++)

            arr[i] = output[i];

    }

  

  

    // Основная функция для этого

    // сортирует arr [] размера n

    // используя Radix Sort

    static void sort(int[] arr, int n)

    {

          

        // Делать подсчет сортировки для первого

        // цифра в базе n. Обратите внимание, что

        // вместо передачи цифр,

        // exp (n ^ 0 = 1) пройдено.

        countSort(arr, n, 1);

  

        // Делаем подсчет за секунду

        // цифра в базе n. Обратите внимание, что

        // вместо передачи цифр,

        // exp (n ^ 1 = n) пройдено.

        countSort(arr, n, n);

    }

  

    // функция полезности

    // напечатать массив

    static void printArr(int[] arr, int n)

    {

        for (int i = 0; i < n; i++)

            Console.Write(arr[i] + " ");

    }

  

    // Код драйвера

    static public void Main ()

    {

          

        // Поскольку размер массива равен 7,

        // элементы должны быть

        // от 0 до 48

        int[] arr = {40, 12, 45, 32, 33, 1, 22};

        int n = arr.Length;

        Console.WriteLine("Given array");

        printArr(arr, n);

  

        sort(arr, n);

  

        Console.WriteLine("\nSorted array");

        printArr(arr, n);

    }

}

  
// Этот код предоставлен Ajit.


Выход:

Given array is
40 12 45 32 33 1 22
Sorted array is
1 12 22 32 33 40 45

Как отсортировать, если диапазон от 1 до 2 ?
Если диапазон от 1 до nn 2 , вышеуказанный процесс не может быть применен напрямую, его необходимо изменить. Рассмотрим n = 100 и диапазон от 1 до 10000. Поскольку основание равно 100, цифра должна быть от 0 до 99, и в числах должно быть 2 цифры. Но число 10000 имеет более 2 цифр. Итак, чтобы отсортировать числа в диапазоне от 1 до n 2 , мы можем использовать следующий процесс.
1) Вычтите все числа на 1.
2) Поскольку диапазон теперь составляет от 0 до n 2 , выполните подсчет сортировки дважды, как это было сделано в приведенной выше реализации.
3) После сортировки элементов добавьте 1 ко всем номерам, чтобы получить исходные номера.

Как отсортировать, если диапазон от 0 до n ^ 3 -1?
Поскольку в базе n может быть 3 цифры, мы должны вызвать сортировку вызовов 3 раза.

Эта статья предоставлена Батишем . Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Сортировать n чисел в диапазоне от 0 до n ^ 2 — 1 за линейное время

0.00 (0%) 0 votes