Requisitos previos: Algoritmo de clasificación rápida
La adaptabilidad en el algoritmo de ordenación rápida se refiere a la decisión de que si se nos da una array que ya está ordenada , entonces las operaciones deben realizarse o no, es decir, si el número de operaciones realizadas en la array ordenada no es igual a las operaciones realizadas en Array sin ordenar, entonces el Algoritmo se conoce como Adaptativo.
En este artículo, veremos si el algoritmo de clasificación rápida es adaptativo o no .
Tomemos un ejemplo:
int arr[] = {1,2,3,4,5};
Entonces, en el ejemplo anterior, podemos ver que la array está ordenada . Pero cuando la array no está ordenada , se debe realizar la operación y, como sabemos, la complejidad temporal de la ordenación rápida es O (N ^ 2) en el peor de los casos. Entonces, si la array no está ordenada, la complejidad de tiempo de la array para ordenar es O (N ^ 2) ,
Motivo : porque para ordenar la array se deben realizar pases N-1 y intercambios Ni-1 .
El algoritmo Quicksort no es adaptativo ,
¿Podemos hacer adaptativo el algoritmo QuickSort?
Sí, podemos hacerlo Adaptativo muy fácilmente.
Por ejemplo:
En el siguiente código, hemos creado una función nula AdaptiveBubbleSort que toma los argumentos «arr[], n» que es una array y su tamaño es n .
Hemos creado la variable isSorted Integer que se Inicializa con 0 , si está ordenada como IsSorted = 1 , entonces el bucle for interno no se ejecutará, pero si no, entonces ejecute el bucle for interno, y además si encontramos un elemento j+ 1 menos que el elemento actual j , luego cámbielos después de intercambiarlos, está ordenado.
Por último, invoque la variable ordenada y devuélvala.
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to print the array
void Print(int arr[], int n)
{
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << endl;
}
// Function for adaptive sort algorithm
// to sort the array if the array is not
// sorted otherwise return in one-pass.
void AdaptiveBubbleSort(int arr[], int n)
{
int temp;
// Stores the status of the array of
// sorted or not.
int isSorted = 0;
// Traverse the array
for (int i = 0; i < n - 1; i++) {
// Initialize it with 1
isSorted = 1;
// Compare the adjacent elements
for (int j = 0; j < n - i - 1; j++) {
// Violates the condition that the
// array is not sorted
if (arr[j] > arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
isSorted = 0;
}
}
// If the array is sorted, then return
// the array and no need to compare elements
if (isSorted) {
return;
}
}
}
// Driver Code
int main()
{
int arr[] = { 1, 2, 3, 4, 5 };
int n = 5;
cout << "Array before sorting : ";
Print(arr, n);
AdaptiveBubbleSort(arr, n);
cout << "Array after sorting : ";
Print(arr, n);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to print the array
static void Print(int arr[], int n)
{
for (int i = 0; i < n; i++) {
System.out.print(arr[i]+ " ");
}
System.out.println();
}
// Function for adaptive sort algorithm
// to sort the array if the array is not
// sorted otherwise return in one-pass.
static void AdaptiveBubbleSort(int arr[], int n)
{
int temp;
// Stores the status of the array of
// sorted or not.
int isSorted = 0;
// Traverse the array
for (int i = 0; i < n - 1; i++) {
// Initialize it with 1
isSorted = 1;
// Compare the adjacent elements
for (int j = 0; j < n - i - 1; j++) {
// Violates the condition that the
// array is not sorted
if (arr[j] > arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
isSorted = 0;
}
}
// If the array is sorted, then return
// the array and no need to compare elements
if (isSorted!=0) {
return;
}
}
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 1, 2, 3, 4, 5 };
int n = 5;
System.out.print("Array before sorting : ");
Print(arr, n);
AdaptiveBubbleSort(arr, n);
System.out.print("Array after sorting : ");
Print(arr, n);
}
}
// This code is contributed by 29AjayKumar
Python3
# Python program for the above approach
# Function to print the array
def Print(arr, n):
for i in range(n):
print(arr[i], end=" ")
print("")
# Function for adaptive sort algorithm
# to sort the array if the array is not
# sorted otherwise return in one-pass.
def AdaptiveBubbleSort(arr, n):
# Stores the status of the array of
# sorted or not.
isSorted = 0
# Traverse the array
for i in range(n - 1):
# Initialize it with 1
isSorted = 1
# Compare the adjacent elements
for j in range(n - i - 1):
# Violates the condition that the
# array is not sorted
if (arr[j] > arr[j + 1]):
temp = arr[j]
arr[j] = arr[j + 1]
arr[j + 1] = temp
isSorted = 0
# If the array is sorted, then return
# the array and no need to compare elements
if (isSorted):
return
# Driver Code
arr = [1, 2, 3, 4, 5]
n = 5
print("Array before sorting : ")
Print(arr, n)
AdaptiveBubbleSort(arr, n)
print("Array after sorting : ")
Print(arr, n)
# This code is contributed by gfgking.
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to print the array
static void Print(int[] arr, int n)
{
for (int i = 0; i < n; i++) {
Console.Write(arr[i]+ " ");
}
Console.WriteLine();
}
// Function for adaptive sort algorithm
// to sort the array if the array is not
// sorted otherwise return in one-pass.
static void AdaptiveBubbleSort(int[] arr, int n)
{
int temp;
// Stores the status of the array of
// sorted or not.
int isSorted = 0;
// Traverse the array
for (int i = 0; i < n - 1; i++) {
// Initialize it with 1
isSorted = 1;
// Compare the adjacent elements
for (int j = 0; j < n - i - 1; j++) {
// Violates the condition that the
// array is not sorted
if (arr[j] > arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
isSorted = 0;
}
}
// If the array is sorted, then return
// the array and no need to compare elements
if (isSorted != 0) {
return;
}
}
}
// Driver Code
public static void Main()
{
int[] arr = { 1, 2, 3, 4, 5 };
int n = 5;
Console.Write("Array before sorting : ");
Print(arr, n);
AdaptiveBubbleSort(arr, n);
Console.Write("Array after sorting : ");
Print(arr, n);
}
}
// This code is contributed by sanjoy_62.
Javascript
<script>
// JavaScript program for the above approach
// Function to print the array
const Print = (arr, n) => {
for (let i = 0; i < n; i++) {
document.write(`${arr[i]} `);
}
document.write("<br/>");
}
// Function for adaptive sort algorithm
// to sort the array if the array is not
// sorted otherwise return in one-pass.
const AdaptiveBubbleSort = (arr, n) => {
let temp;
// Stores the status of the array of
// sorted or not.
let isSorted = 0;
// Traverse the array
for (let i = 0; i < n - 1; i++) {
// Initialize it with 1
isSorted = 1;
// Compare the adjacent elements
for (let j = 0; j < n - i - 1; j++) {
// Violates the condition that the
// array is not sorted
if (arr[j] > arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
isSorted = 0;
}
}
// If the array is sorted, then return
// the array and no need to compare elements
if (isSorted) {
return;
}
}
}
// Driver Code
let arr = [1, 2, 3, 4, 5];
let n = 5;
document.write("Array before sorting : ");
Print(arr, n);
AdaptiveBubbleSort(arr, n);
document.write("Array after sorting : ");
Print(arr, n);
// This code is contributed by rakeshsahni
</script>
Array before sorting : 1 2 3 4 5 Array after sorting : 1 2 3 4 5
Por lo tanto, si la array ya está ordenada, cada elemento se recorre casi una vez. Por lo tanto, la complejidad del tiempo se convierte en O(N) y, en caso contrario, toma O(N*log(N)).
En todos los casos el Espacio Auxiliar será O(1).
Publicación traducida automáticamente
Artículo escrito por mayank007rawa y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA