Самые медленные алгоритмы сортировки

Опубликовано: 5 Января, 2022

Алгоритм сортировки используется для переупорядочивания заданного массива или элементов списка в соответствии с оператором сравнения элементов. Оператор сравнения используется для определения нового порядка элемента в соответствующей структуре данных. Но ниже приведены некоторые из самых медленных алгоритмов сортировки:

Сортировка Stooge: сортировка Stooge - это рекурсивный алгоритм сортировки. Он рекурсивно делит и сортирует массив по частям. Ниже приведены этапы сортировки Stooge:

  • Если значение в индексе 0 больше, чем значение в последнем индексе, поменяйте их местами.
  • Если количество элементов в массиве больше двух:
    • Рекурсивно вызывать функцию stoogesort для начальных 2/3 элементов массива.
    • Рекурсивно вызывать функцию stoogesort для последних 2/3 элементов массива.
    • Рекурсивно вызовите функцию stoogesort для начальных 2/3 элементов снова, чтобы убедиться, что результирующий массив отсортирован или нет.
  • Распечатайте отсортированный массив.

Ниже представлена реализация описанного выше подхода:

C ++

// C++ program for the stooge sort
#include <iostream>
using namespace std;
// Function to implement stooge sort
void stoogesort( int arr[], int l, int h)
{
// Base Case
if (l >= h)
return ;
// If first element is smaller than
// last element, swap them
if (arr[l] > arr[h])
swap(arr[l], arr[h]);
// If there are more than 2 elements
// in the array
if (h - l + 1 > 2) {
int t = (h - l + 1) / 3;
// Recursively sort the first
// 2/3 elements
stoogesort(arr, l, h - t);
// Recursively sort the last
// 2/3 elements
stoogesort(arr, l + t, h);
// Recursively sort the first
// 2/3 elements again
stoogesort(arr, l, h - t);
}
}
// Driver Code
int main()
{
int arr[] = { 2, 4, 5, 3, 1 };
int N = sizeof (arr) / sizeof (arr[0]);
// Function Call
stoogesort(arr, 0, N - 1);
// Display the sorted array
for ( int i = 0; i < N; i++) {
cout << arr[i] << " " ;
}
return 0;
}

Джава

// Java program for the
// stooge sort
class GFG{
// Function to implement
// stooge sort
static void stoogesort( int arr[],
int l, int h)
{
// Base Case
if (l >= h)
return ;
// If first element is smaller
// than last element, swap them
if (arr[l] > arr[h])
{
int temp = arr[l];
arr[l] = arr[h];
arr[h] = temp;
}
// If there are more than
// 2 elements in the array
if (h - l + 1 > 2 )
{
int t = (h - l + 1 ) / 3 ;
// Recursively sort the
// first 2/3 elements
stoogesort(arr, l, h - t);
// Recursively sort the
// last 2/3 elements
stoogesort(arr, l + t, h);
// Recursively sort the
// first 2/3 elements again
stoogesort(arr, l, h - t);
}
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 2 , 4 , 5 , 3 , 1 };
int N = arr.length;
// Function Call
stoogesort(arr, 0 , N - 1 );
// Display the sorted array
for ( int i = 0 ; i < N; i++)
{
System.out.print(arr[i] + " " );
}
}
}
// This code is contributed by Chitranayal

Python3

# Python3 program for the stooge sort
# Function to implement stooge sort
def stoogesort(arr, l, h):
# Base Case
if (l > = h):
return
# If first element is smaller than
# last element, swap them
if (arr[l] > arr[h]):
temp = arr[l]
arr[l] = arr[h]
arr[h] = temp
# If there are more than 2 elements
# in the array
if (h - l + 1 > 2 ):
t = (h - l + 1 ) / / 3
# Recursively sort the first
# 2/3 elements
stoogesort(arr, l, h - t)
# Recursively sort the last
# 2/3 elements
stoogesort(arr, l + t, h)
# Recursively sort the first
# 2/3 elements again
stoogesort(arr, l, h - t)
# Driver Code
arr = [ 2 , 4 , 5 , 3 , 1 ]
N = len (arr)
# Function Call
stoogesort(arr, 0 , N - 1 )
# Display the sorted array
for i in range (N):
print (arr[i], end = " " )
# This code is contributed by code_hunt

C #

// C# program for the
// stooge sort
using System;
class GFG{
// Function to implement
// stooge sort
static void stoogesort( int []arr,
int l, int h)
{
// Base Case
if (l >= h)
return ;
// If first element is smaller
// than last element, swap them
if (arr[l] > arr[h])
{
int temp = arr[l];
arr[l] = arr[h];
arr[h] = temp;
}
// If there are more than
// 2 elements in the array
if (h - l + 1 > 2)
{
int t = (h - l + 1) / 3;
// Recursively sort the
// first 2/3 elements
stoogesort(arr, l, h - t);
// Recursively sort the
// last 2/3 elements
stoogesort(arr, l + t, h);
// Recursively sort the
// first 2/3 elements again
stoogesort(arr, l, h - t);
}
}
// Driver Code
public static void Main(String[] args)
{
int []arr = {2, 4, 5, 3, 1};
int N = arr.Length;
// Function Call
stoogesort(arr, 0, N - 1);
// Display the sorted array
for ( int i = 0; i < N; i++)
{
Console.Write(arr[i] + " " );
}
}
}
// This code is contributed by Princi Singh
Выход:
 1 2 3 4 5

Сложность времени: O (N 2.709 ). Следовательно, он медленнее, чем даже пузырьковая сортировка с временной сложностью O (N 2 ).

Медленная сортировка: медленная сортировка - это пример шутливой шутки «Умножай и сдавайся» о разделении и победе . Медленная сортировка сохраняет максимальный элемент массива в последней позиции, рекурсивно делит массив пополам и сравнивает каждый из них. Затем он рекурсивно вызывает массив без предыдущего максимального элемента и сохраняет новый максимальный элемент в новой последней позиции. Ниже приведены шаги медленной сортировки:

  1. Найдите максимум массива и поместите его в конец массива с помощью
    1. Рекурсивно вызывать функцию slowsort для максимума первых N / 2 элементов .
    2. Рекурсивно вызвать функцию slowsort для максимума из оставшихся N / 2 элементов .
    3. Найдите самый большой из этих двух максимумов и сохраните его в конце.
    4. Рекурсивно вызывать функцию slowsort для всего массива, кроме максимума.
  2. Распечатайте отсортированный массив.

Ниже представлена реализация описанного выше подхода:

C ++

// C++ program to implement Slow sort
#include <bits/stdc++.h>
using namespace std;
// Function for swap two numbers using
// pointers
void swap( int * xp, int * yp)
{
int temp = *xp;
*xp = *yp;
*yp = temp;
}
// Function that implements Slow Sort
void slowSort( int A[], int i, int j)
{
// Base Case
if (i >= j)
return ;
// Middle value
int m = (i + j) / 2;
// Recursively call with left half
slowSort(A, i, m);
// Recursively call with right half
slowSort(A, m + 1, j);
// Swap if first element
// is lower than second
if (A[j] < A[m]) {
swap(&A[j], &A[m]);
}
// Recursively call with whole
// array except maximum element
slowSort(A, i, j - 1);
}
// Function to print the array
void printArray( int arr[], int size)
{
int i;
for (i = 0; i < size; i++)
cout << arr[i] << " " ;
cout << endl;
}
// Driver Code
int main()
{
int arr[] = { 6, 8, 9, 4, 12, 1 };
int N = sizeof (arr) / sizeof (arr[0]);
// Function call
slowSort(arr, 0, N - 1);
// Display the sorted array
printArray(arr, N);
return 0;
}

Джава

// Java program to implement Slow sort
import java.util.*;
class GFG
{
// Function that implements Slow Sort
static void slowSort( int A[], int i, int j)
{
// Base Case
if (i >= j)
return ;
// Middle value
int m = (i + j) / 2 ;
// Recursively call with left half
slowSort(A, i, m);
// Recursively call with right half
slowSort(A, m + 1 , j);
// Swap if first element
// is lower than second
if (A[j] < A[m])
{
int temp = A[j];
A[j] = A[m];
A[m] = temp;
}
// Recursively call with whole
// array except maximum element
slowSort(A, i, j - 1 );
}
// Function to print the array
static void printArray( int arr[], int size)
{
int i;
for (i = 0 ; i < size; i++)
System.out.print(arr[i]+ " " );
System.out.println();
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 6 , 8 , 9 , 4 , 12 , 1 };
int N = arr.length;
// Function call
slowSort(arr, 0 , N - 1 );
// Display the sorted array
printArray(arr, N);
}
}
// This code is contributed by 29AjayKumar

Python3

# Python program to implement Slow sort
# Function that implements Slow Sort
def slowSort(A, i, j):
# Base Case
if (i > = j):
return ;
# Middle value
m = (i + j) / / 2 ;
# Recursively call with left half
slowSort(A, i, m);
# Recursively call with right half
slowSort(A, m + 1 , j);
# Swap if first element
# is lower than second
if (A[j] < A[m]):
temp = A[j];
A[j] = A[m];
A[m] = temp;
# Recursively call with whole
# array except maximum element
slowSort(A, i, j - 1 );
# Function to prthe array
def printArray(arr, size):
i = 0 ;
for i in range (size):
print (arr[i], end = " " );
print ();
# Driver Code
if __name__ = = '__main__' :
arr = [ 6 , 8 , 9 , 4 , 12 , 1 ];
N = len (arr);
# Function call
slowSort(arr, 0 , N - 1 );
# Display the sorted array
printArray(arr, N);
# This code contributed by gauravrajput1

C #

// C# program to implement Slow sort
using System;
class GFG
{
// Function that implements Slow Sort
static void slowSort( int []A, int i, int j)
{
// Base Case
if (i >= j)
return ;
// Middle value
int m = (i + j) / 2;
// Recursively call with left half
slowSort(A, i, m);
// Recursively call with right half
slowSort(A, m + 1, j);
// Swap if first element
// is lower than second
if (A[j] < A[m])
{
int temp = A[j];
A[j] = A[m];
A[m] = temp;
}
// Recursively call with whole
// array except maximum element
slowSort(A, i, j - 1);
}
// Function to print the array
static void printArray( int []arr, int size)
{
int i;
for (i = 0; i < size; i++)
Console.Write(arr[i] + " " );
Console.WriteLine();
}
// Driver Code
public static void Main(String[] args)
{
int []arr = { 6, 8, 9, 4, 12, 1 };
int N = arr.Length;
// Function call
slowSort(arr, 0, N - 1);
// Display the sorted array
printArray(arr, N);
}
}
// This code is contributed by 29AjayKumar
Выход:
 1 4 6 8 9 12

Сложность времени:

  • Базовый случай: O (N ((log N) / (2 + e)), где, e> 0
  • Средний случай: O (N (log (N) / 2) )

Даже лучший случай хуже, чем пузырьковая сортировка. Он менее эффективен, чем сортировка Stooge.

Сортировка сна: Ниже приведены шаги сортировки Stooge:

  1. Создайте разные потоки для каждого из элементов входного массива, а затем каждый поток «спит» на время, пропорциональное значению соответствующего элемента массива.
  2. Поток, у которого меньше всего времени сна, просыпается первым, и печатается число, а затем второй наименьший элемент и так далее.
  3. Самый большой элемент просыпается через долгое время, а затем печатается последний элемент. Таким образом, вывод является отсортированным.

Весь этот процесс многопоточности происходит в фоновом режиме и в ядре ОС.

Ниже представлена реализация описанного выше подхода:

Статьи Алгоритмы

РЕКОМЕНДУЕМЫЕ СТАТЬИ

Онлайн-обменники: быстрый и удобный способ конвертации активов в современном мире
17 Апреля, 2024
Лучшие онлайн-курсы по WordPress: рейтинг 2024
29 Марта, 2024
Для кого буду полезны услуги SMS-центра
24 Марта, 2024
Что такое экспертиза исходного кода и как ее проводят?
3 Марта, 2024
Как добавить деньги на счет аккаунта Steam через криптовалюту
20 Февраля, 2024
Заказать докторскую диссертацию на заказ
30 Января, 2024
Купить лайки в ВК: зачем, сколько и где
19 Января, 2024
Как добавить деньги на свой аккаунт в Steam и начать покупать игры и контент
12 Января, 2024