Introsort
Introsort is a hybrid sorting algorithm that combines two different sorting algorithms to achieve a fast and efficient sorting process. It starts with quicksort, which is a well-known sorting algorithm, and switches to heapsort when the recursion depth exceeds a certain threshold. This threshold is determined by the size of the array being sorted and the maximum depth of the recursion tree.
The basic idea behind introsort is to take advantage of the strengths of each of the two algorithms and avoid their weaknesses. Quicksort has a very fast average-case performance and is well suited for small to medium sized arrays, but it can have a worst-case performance of O(n^2) for certain inputs. Heapsort, on the other hand, has a worst-case performance of O(n log n) but can be slower than quicksort for small arrays.
Introsort is designed to overcome the weaknesses of quicksort and heapsort by using quicksort for small arrays and switching to heapsort for larger ones. The threshold value for switching to heapsort is typically set to a value that ensures that quicksort will have good performance for most inputs, while still avoiding the worst-case behavior.
In summary, introsort combines quicksort and heapsort to achieve a fast and efficient sorting algorithm. It uses quicksort for small arrays and switches to heapsort for larger ones to avoid the worst-case performance of quicksort while maintaining its fast average-case performance.
Here given code implementation process.
// C Program
// Sort array elements by using introsort
#include <stdio.h>
#include <math.h>
//Function which is display arr elements
void display(int arr[], int size)
{
for (int i = 0; i < size; ++i)
{
printf(" %d", arr[i]);
}
printf("\n");
}
// Swapping the array elements in given location
void swap_data(int arr[], int first, int second)
{
int temp = arr[first];
arr[first] = arr[second];
arr[second] = temp;
}
// Perform the insertion sort in given array
void insertion_sort(int arr[], int size)
{
int i = 0;
int j = 0;
for (i = 0; i < size - 1; ++i)
{
j = i + 1;
while (j > 0 && arr[j - 1] > arr[j])
{
//Swap array element
swap_data(arr, j, j - 1);
j--;
}
}
}
int partition(int arr[], int low, int high)
{
//Set the high index element to its proper sorted position
int pv = arr[high];
int i = low - 1;
for (int j = low; j < high; ++j)
{
if (arr[j] < pv)
{
i++;
swap_data(arr, i, j);
}
}
//set the high index value to its sorted position
swap_data(arr, i + 1, high);
//returns the next sorting element location
return i + 1;
}
//Perform the quick sort in given array
void quick_sort(int arr[], int low, int high)
{
if (low < high)
{
//Get the pivot element
int pv = partition(arr, low, high);
quick_sort(arr, low, pv - 1);
quick_sort(arr, pv + 1, high);
}
}
int find_pivot(int arr[], int a, int b, int c)
{
if (arr[a] < arr[b] && arr[b] < arr[c])
{
return b;
}
else if (arr[c] <= arr[b] && arr[b] <= arr[a])
{
return b;
}
else if (arr[b] < arr[c] && arr[c] <= arr[a])
{
return c;
}
else if (arr[a] < arr[c] && arr[c] <= arr[b])
{
return c;
}
else if (arr[b] <= arr[a] && arr[a] < arr[c])
{
return a;
}
else if (arr[c] <= arr[a] && arr[a] < arr[b])
{
return a;
}
}
int compare(int arr[], int left, int right, int root, int size)
{
int location = -1;
if (left < size && arr[left] > arr[root])
{
if (right < size && arr[right] > arr[left])
{
swap_data(arr, right, root);
location = right;
}
else
{
swap_data(arr, left, root);
location = left;
}
}
else if (right < size && arr[right] > arr[root])
{
swap_data(arr, right, root);
location = right;
}
return location;
}
//Perform the operation of heap sort
void heap(int arr[], int size, int root)
{
int left, right;
while (root != -1)
{
left = 2 * root + 1;
right = 2 * root + 2;
root = compare(arr, left, right, root, size);
}
}
//Sort array element using heap sort
void heap_sort(int arr[], int size)
{
for (int i = (size / 2) - 1; i >= 0; i--)
{
heap(arr, size, i);
}
for (int i = size - 1; i >= 0; i--)
{
swap_data(arr, 0, i);
heap(arr, i, 0);
}
}
//Perform the introsort in given array
void execute_introsort(int arr[], int front, int tail, int deep)
{
int size = tail - front;
if (size < 16)
{
insertion_sort(arr, tail + 1);
}
else if (deep == 0)
{
//when heap sort are work
heap_sort(arr, tail + 1);
}
else
{
//When executed of quick sort
int pivot = find_pivot(arr, front, front + ((tail - front) / 2) + 1, tail);
swap_data(arr, pivot, tail);
int point = partition(arr, front, tail);
execute_introsort(arr, front, point - 1, deep - 1);
execute_introsort(arr, point + 1, tail, deep - 1);
}
}
//Handling the request of introsort
void introsort(int arr[], int size)
{
int deep = 2 * log(size - 1);
execute_introsort(arr, 0, size - 1, deep);
}
int main()
{
//Define an array of integers
int arr[] = {
11,
8,
3,
8,
12,
-1,
-3,
1,
4,
7,
5
};
//Get the size of arr
int size = sizeof(arr) / sizeof(arr[0]);
//Before sort
printf("\n Before Sort :\n");
display(arr, size);
//Sort element
introsort(arr, size);
//After sort
printf("\n After Sort :\n");
display(arr, size);
int arr1[] = {
9,
-3,
5,
1,
7,
9,
3,
4,
5,
2,
4,
7,
8,
-4,
6,
34,
43,
2,
7,
8,
11,
12,
9,
-6,
2
};
//Get the size of arr
size = sizeof(arr1) / sizeof(arr1[0]);
//Before sort
printf("\n Before Sort :\n");
display(arr1, size);
//Sort element
introsort(arr1, size);
//After sort
printf("\n After Sort :\n");
display(arr1, size);
return 0;
}Output
Before Sort :
11 8 3 8 12 -1 -3 1 4 7 5
After Sort :
-3 -1 1 3 4 5 7 8 8 11 12
Before Sort :
9 -3 5 1 7 9 3 4 5 2 4 7 8 -4 6 34 43 2 7 8 11 12 9 -6 2
After Sort :
-6 -4 -3 1 2 2 2 3 4 4 5 5 6 7 7 7 8 8 9 9 9 11 12 34 43/*
Java Program
Sort array elements by using introsort
*/
class MySort
{
//Function which is display arr elements
public void display(int[] arr, int size)
{
for (int i = 0; i < size; ++i)
{
System.out.print(" " + arr[i]);
}
System.out.print("\n");
}
// Swapping the array elements in given location
public void swap_data(int[] arr, int first, int second)
{
int temp = arr[first];
arr[first] = arr[second];
arr[second] = temp;
}
// Perform the insertion sort in given array
public void insertion_sort(int[] arr, int size)
{
int i = 0;
int j = 0;
for (i = 0; i < size - 1; ++i)
{
j = i + 1;
while (j > 0 && arr[j - 1] > arr[j])
{
//Swap array element
swap_data(arr, j, j - 1);
j--;
}
}
}
public int partition(int[] arr, int low, int high)
{
//Set the high index element to its proper sorted position
int pv = arr[high];
int i = low - 1;
for (int j = low; j < high; ++j)
{
if (arr[j] < pv)
{
i++;
swap_data(arr, i, j);
}
}
//set the high index value to its sorted position
swap_data(arr, i + 1, high);
//returns the next sorting element location
return i + 1;
}
//Perform the quick sort in given array
public void quick_sort(int[] arr, int low, int high)
{
if (low < high)
{
//Get the pivot element
int pv = partition(arr, low, high);
quick_sort(arr, low, pv - 1);
quick_sort(arr, pv + 1, high);
}
}
public int find_pivot(int[] arr, int a, int b, int c)
{
if (arr[a] < arr[b] && arr[b] < arr[c])
{
return b;
}
else if (arr[c] <= arr[b] && arr[b] <= arr[a])
{
return b;
}
else if (arr[b] < arr[c] && arr[c] <= arr[a])
{
return c;
}
else if (arr[a] < arr[c] && arr[c] <= arr[b])
{
return c;
}
else if (arr[b] <= arr[a] && arr[a] < arr[c])
{
return a;
}
else
{
return a;
}
}
public int compare(int[] arr, int left, int right, int root, int size)
{
int location = -1;
if (left < size && arr[left] > arr[root])
{
if (right < size && arr[right] > arr[left])
{
swap_data(arr, right, root);
location = right;
}
else
{
swap_data(arr, left, root);
location = left;
}
}
else if (right < size && arr[right] > arr[root])
{
swap_data(arr, right, root);
location = right;
}
return location;
}
//Perform the operation of heap sort
public void heap(int[] arr, int size, int root)
{
int left, right;
while (root != -1)
{
left = 2 * root + 1;
right = 2 * root + 2;
root = compare(arr, left, right, root, size);
}
}
//Sort array element using heap sort
public void heap_sort(int[] arr, int size)
{
for (int i = (size / 2) - 1; i >= 0; i--)
{
heap(arr, size, i);
}
for (int i = size - 1; i >= 0; i--)
{
swap_data(arr, 0, i);
heap(arr, i, 0);
}
}
//Perform the introsort in given array
public void execute_introsort(int[] arr, int front, int tail, int deep)
{
int size = tail - front;
if (size < 16)
{
insertion_sort(arr, tail + 1);
}
else if (deep == 0)
{
//when heap sort are work
heap_sort(arr, tail + 1);
}
else
{
//When executed of quick sort
int pivot = find_pivot(arr, front, front + ((tail - front) / 2) + 1, tail);
swap_data(arr, pivot, tail);
int point = partition(arr, front, tail);
execute_introsort(arr, front, point - 1, deep - 1);
execute_introsort(arr, point + 1, tail, deep - 1);
}
}
//Handling the request of introsort
public void introsort(int[] arr, int size)
{
int deep = (int)(2 * Math.floor(Math.log(size) / Math.log(2)));
execute_introsort(arr, 0, size - 1, deep);
}
public static void main(String[] args)
{
MySort obj = new MySort();
//Define an array of integers
int[] arr = {
11,
8,
3,
8,
12,
-1,
-3,
1,
4,
7,
5
};
//Get the size
int size = arr.length;;
System.out.print("\n Befre Sort :\n");
obj.display(arr, size);
//Sort element
obj.introsort(arr, size);
System.out.print("\n After Sort :\n");
obj.display(arr, size);
int[] arr1 = {
9,
-3,
5,
1,
7,
9,
3,
4,
5,
2,
4,
7,
8,
-4,
6,
34,
43,
2,
7,
8,
11,
12,
9,
-6,
2
};
//Get the size
size = arr1.length;
System.out.print("\n Before Sort :\n");
obj.display(arr1, size);
//Sort element
obj.introsort(arr1, size);
System.out.print("\n After Sort :\n");
obj.display(arr1, size);
}
}Output
Befre Sort :
11 8 3 8 12 -1 -3 1 4 7 5
After Sort :
-3 -1 1 3 4 5 7 8 8 11 12
Before Sort :
9 -3 5 1 7 9 3 4 5 2 4 7 8 -4 6 34 43 2 7 8 11 12 9 -6 2
After Sort :
-6 -4 -3 1 2 2 2 3 4 4 5 5 6 7 7 7 8 8 9 9 9 11 12 34 43//Include header file
#include <iostream>
#include<math.h>
using namespace std;
/*
C++ Program
Sort array elements by using introsort
*/
class MySort
{
public:
//Function which is display arr elements
void display(int arr[], int size)
{
for (int i = 0; i < size; ++i)
{
cout << " " << arr[i];
}
cout << "\n";
}
// Swapping the array elements in given location
void swap_data(int arr[], int first, int second)
{
int temp = arr[first];
arr[first] = arr[second];
arr[second] = temp;
}
// Perform the insertion sort in given array
void insertion_sort(int arr[], int size)
{
int i = 0;
int j = 0;
for (i = 0; i < size - 1; ++i)
{
j = i + 1;
while (j > 0 && arr[j - 1] > arr[j])
{
//Swap array element
this->swap_data(arr, j, j - 1);
j--;
}
}
}
int partition(int arr[], int low, int high)
{
//Set the high index element to its proper sorted position
int pv = arr[high];
int i = low - 1;
for (int j = low; j < high; ++j)
{
if (arr[j] < pv)
{
i++;
this->swap_data(arr, i, j);
}
}
//set the high index value to its sorted position
this->swap_data(arr, i + 1, high);
//returns the next sorting element location
return i + 1;
}
//Perform the quick sort in given array
void quick_sort(int arr[], int low, int high)
{
if (low < high)
{
//Get the pivot element
int pv = this->partition(arr, low, high);
this->quick_sort(arr, low, pv - 1);
this->quick_sort(arr, pv + 1, high);
}
}
int find_pivot(int arr[], int a, int b, int c)
{
if (arr[a] < arr[b] && arr[b] < arr[c])
{
return b;
}
else if (arr[c] <= arr[b] && arr[b] <= arr[a])
{
return b;
}
else if (arr[b] < arr[c] && arr[c] <= arr[a])
{
return c;
}
else if (arr[a] < arr[c] && arr[c] <= arr[b])
{
return c;
}
else if (arr[b] <= arr[a] && arr[a] < arr[c])
{
return a;
}
else
{
return a;
}
}
int compare(int arr[], int left, int right, int root, int size)
{
int location = -1;
if (left < size && arr[left] > arr[root])
{
if (right < size && arr[right] > arr[left])
{
this->swap_data(arr, right, root);
location = right;
}
else
{
this->swap_data(arr, left, root);
location = left;
}
}
else if (right < size && arr[right] > arr[root])
{
this->swap_data(arr, right, root);
location = right;
}
return location;
}
//Perform the operation of heap sort
void heap(int arr[], int size, int root)
{
int left, right;
while (root != -1)
{
left = 2 * root + 1;
right = 2 * root + 2;
root = this->compare(arr, left, right, root, size);
}
}
//Sort array element using heap sort
void heap_sort(int arr[], int size)
{
for (int i = (size / 2) - 1; i >= 0; i--)
{
this->heap(arr, size, i);
}
for (int i = size - 1; i >= 0; i--)
{
this->swap_data(arr, 0, i);
this->heap(arr, i, 0);
}
}
//Perform the introsort in given array
void execute_introsort(int arr[], int front, int tail, int deep)
{
int size = tail - front;
if (size < 16)
{
this->insertion_sort(arr, tail + 1);
}
else if (deep == 0)
{
//when heap sort are work
this->heap_sort(arr, tail + 1);
}
else
{
//When executed of quick sort
int pivot = this->find_pivot(arr, front, front + ((tail - front) / 2) + 1, tail);
this->swap_data(arr, pivot, tail);
int point = this->partition(arr, front, tail);
this->execute_introsort(arr, front, point - 1, deep - 1);
this->execute_introsort(arr, point + 1, tail, deep - 1);
}
}
//Handling the request of introsort
void introsort(int arr[], int size)
{
int deep = (int)(2 * floor(log(size) / log(2)));
this->execute_introsort(arr, 0, size - 1, deep);
}
};
int main()
{
MySort obj = MySort();
int arr[] = {
11 , 8 , 3 , 8 , 12 , -1 , -3 , 1 , 4 , 7 , 5
};
//Get the size
int size = sizeof(arr) / sizeof(arr[0]);;
cout << "\n Befre Sort :\n";
obj.display(arr, size);
//Sort element
obj.introsort(arr, size);
cout << "\n After Sort :\n";
obj.display(arr, size);
int arr1[] = {
9 , -3 , 5 , 1 , 7 , 9 , 3 , 4 , 5 , 2 , 4 , 7 , 8 , -4 , 6 , 34 , 43 , 2 , 7 , 8 , 11 , 12 , 9 , -6 , 2
};
//Get the size
size = sizeof(arr1) / sizeof(arr1[0]);
cout << "\n Before Sort :\n";
obj.display(arr1, size);
//Sort element
obj.introsort(arr1, size);
cout << "\n After Sort :\n";
obj.display(arr1, size);
return 0;
}Output
Befre Sort :
11 8 3 8 12 -1 -3 1 4 7 5
After Sort :
-3 -1 1 3 4 5 7 8 8 11 12
Before Sort :
9 -3 5 1 7 9 3 4 5 2 4 7 8 -4 6 34 43 2 7 8 11 12 9 -6 2
After Sort :
-6 -4 -3 1 2 2 2 3 4 4 5 5 6 7 7 7 8 8 9 9 9 11 12 34 43//Include namespace system
using System;
/*
C# Program
Sort array elements by using introsort
*/
class MySort
{
//Function which is display arr elements
public void display(int[] arr, int size)
{
for (int i = 0; i < size; ++i)
{
Console.Write(" " + arr[i]);
}
Console.Write("\n");
}
// Swapping the array elements in given location
public void swap_data(int[] arr, int first, int second)
{
int temp = arr[first];
arr[first] = arr[second];
arr[second] = temp;
}
// Perform the insertion sort in given array
public void insertion_sort(int[] arr, int size)
{
int i = 0;
int j = 0;
for (i = 0; i < size - 1; ++i)
{
j = i + 1;
while (j > 0 && arr[j - 1] > arr[j])
{
//Swap array element
swap_data(arr, j, j - 1);
j--;
}
}
}
public int partition(int[] arr, int low, int high)
{
//Set the high index element to its proper sorted position
int pv = arr[high];
int i = low - 1;
for (int j = low; j < high; ++j)
{
if (arr[j] < pv)
{
i++;
swap_data(arr, i, j);
}
}
//set the high index value to its sorted position
swap_data(arr, i + 1, high);
//returns the next sorting element location
return i + 1;
}
//Perform the quick sort in given array
public void quick_sort(int[] arr, int low, int high)
{
if (low < high)
{
//Get the pivot element
int pv = partition(arr, low, high);
quick_sort(arr, low, pv - 1);
quick_sort(arr, pv + 1, high);
}
}
public int find_pivot(int[] arr, int a, int b, int c)
{
if (arr[a] < arr[b] && arr[b] < arr[c])
{
return b;
}
else if (arr[c] <= arr[b] && arr[b] <= arr[a])
{
return b;
}
else if (arr[b] < arr[c] && arr[c] <= arr[a])
{
return c;
}
else if (arr[a] < arr[c] && arr[c] <= arr[b])
{
return c;
}
else if (arr[b] <= arr[a] && arr[a] < arr[c])
{
return a;
}
else
{
return a;
}
}
public int compare(int[] arr, int left, int right, int root, int size)
{
int location = -1;
if (left < size && arr[left] > arr[root])
{
if (right < size && arr[right] > arr[left])
{
swap_data(arr, right, root);
location = right;
}
else
{
swap_data(arr, left, root);
location = left;
}
}
else if (right < size && arr[right] > arr[root])
{
swap_data(arr, right, root);
location = right;
}
return location;
}
//Perform the operation of heap sort
public void heap(int[] arr, int size, int root)
{
int left, right;
while (root != -1)
{
left = 2 * root + 1;
right = 2 * root + 2;
root = compare(arr, left, right, root, size);
}
}
//Sort array element using heap sort
public void heap_sort(int[] arr, int size)
{
for (int i = (size / 2) - 1; i >= 0; i--)
{
heap(arr, size, i);
}
for (int i = size - 1; i >= 0; i--)
{
swap_data(arr, 0, i);
heap(arr, i, 0);
}
}
//Perform the introsort in given array
public void execute_introsort(int[] arr, int front, int tail, int deep)
{
int size = tail - front;
if (size < 16)
{
insertion_sort(arr, tail + 1);
}
else if (deep == 0)
{
//when heap sort are work
heap_sort(arr, tail + 1);
}
else
{
//When executed of quick sort
int pivot = find_pivot(arr, front, front + ((tail - front) / 2) + 1, tail);
swap_data(arr, pivot, tail);
int point = partition(arr, front, tail);
execute_introsort(arr, front, point - 1, deep - 1);
execute_introsort(arr, point + 1, tail, deep - 1);
}
}
//Handling the request of introsort
public void introsort(int[] arr, int size)
{
int deep = (int)(2 * Math.Floor(Math.Log(size) / Math.Log(2)));
execute_introsort(arr, 0, size - 1, deep);
}
public static void Main(String[] args)
{
MySort obj = new MySort();
int[] arr = {
11 , 8 , 3 , 8 , 12 , -1 , -3 , 1 , 4 , 7 , 5
};
//Get the size
int size = arr.Length;;
Console.Write("\n Befre Sort :\n");
obj.display(arr, size);
//Sort element
obj.introsort(arr, size);
Console.Write("\n After Sort :\n");
obj.display(arr, size);
int[] arr1 = {
9 , -3 , 5 , 1 , 7 , 9 , 3 , 4 , 5 , 2 , 4 , 7 , 8 , -4 , 6 , 34 , 43 , 2 , 7 , 8 , 11 , 12 , 9 , -6 , 2
};
//Get the size
size = arr1.Length;
Console.Write("\n Before Sort :\n");
obj.display(arr1, size);
//Sort element
obj.introsort(arr1, size);
Console.Write("\n After Sort :\n");
obj.display(arr1, size);
}
}Output
Befre Sort :
11 8 3 8 12 -1 -3 1 4 7 5
After Sort :
-3 -1 1 3 4 5 7 8 8 11 12
Before Sort :
9 -3 5 1 7 9 3 4 5 2 4 7 8 -4 6 34 43 2 7 8 11 12 9 -6 2
After Sort :
-6 -4 -3 1 2 2 2 3 4 4 5 5 6 7 7 7 8 8 9 9 9 11 12 34 43<?php
/*
Php Program
Sort array elements by using introsort
*/
class MySort
{
//Function which is display arr elements
public function display($arr, $size)
{
for ($i = 0; $i < $size; ++$i)
{
echo " ". $arr[$i];
}
echo "\n";
}
// Swapping the array elements in given location
public function swap_data( & $arr, $first, $second)
{
$temp = $arr[$first];
$arr[$first] = $arr[$second];
$arr[$second] = $temp;
}
// Perform the insertion sort in given array
public function insertion_sort( & $arr, $size)
{
$i = 0;
$j = 0;
for ($i = 0; $i < $size - 1; ++$i)
{
$j = $i + 1;
while ($j > 0 && $arr[$j - 1] > $arr[$j])
{
//Swap array element
$this->swap_data($arr, $j, $j - 1);
$j--;
}
}
}
public function partition( & $arr, $low, $high)
{
//Set the high index element to its proper sorted position
$pv = $arr[$high];
$i = $low - 1;
for ($j = $low; $j < $high; ++$j)
{
if ($arr[$j] < $pv)
{
$i++;
$this->swap_data($arr, $i, $j);
}
}
//set the high index value to its sorted position
$this->swap_data($arr, $i + 1, $high);
//returns the next sorting element location
return $i + 1;
}
//Perform the quick sort in given array
public function quick_sort( & $arr, $low, $high)
{
if ($low < $high)
{
//Get the pivot element
$pv = $this->partition($arr, $low, $high);
$this->quick_sort($arr, $low, $pv - 1);
$this->quick_sort($arr, $pv + 1, $high);
}
}
public function find_pivot( & $arr, $a, $b, $c)
{
if ($arr[$a] < $arr[$b] && $arr[$b] < $arr[$c])
{
return $b;
}
else if ($arr[$c] <= $arr[$b] && $arr[$b] <= $arr[$a])
{
return $b;
}
else if ($arr[$b] < $arr[$c] && $arr[$c] <= $arr[$a])
{
return $c;
}
else if ($arr[$a] < $arr[$c] && $arr[$c] <= $arr[$b])
{
return $c;
}
else if ($arr[$b] <= $arr[$a] && $arr[$a] < $arr[$c])
{
return $a;
}
else
{
return $a;
}
}
public function compare( & $arr, $left, $right, $root, $size)
{
$location = -1;
if ($left < $size && $arr[$left] > $arr[$root])
{
if ($right < $size && $arr[$right] > $arr[$left])
{
$this->swap_data($arr, $right, $root);
$location = $right;
}
else
{
$this->swap_data($arr, $left, $root);
$location = $left;
}
}
else if ($right < $size && $arr[$right] > $arr[$root])
{
$this->swap_data($arr, $right, $root);
$location = $right;
}
return $location;
}
//Perform the operation of heap sort
public function heap( & $arr, $size, $root)
{
$left;
$right;
while ($root != -1)
{
$left = 2 * $root + 1;
$right = 2 * $root + 2;
$root = $this->compare($arr, $left, $right, $root, $size);
}
}
//Sort array element using heap sort
public function heap_sort( & $arr, $size)
{
for ($i = (intval($size / 2)) - 1; $i >= 0; $i--)
{
$this->heap($arr, $size, $i);
}
for ($i = $size - 1; $i >= 0; $i--)
{
$this->swap_data($arr, 0, $i);
$this->heap($arr, $i, 0);
}
}
//Perform the introsort in given array
public function execute_introsort( & $arr, $front, $tail, $deep)
{
$size = $tail - $front;
if ($size < 16)
{
$this->insertion_sort($arr, $tail + 1);
}
else if ($deep == 0)
{
//when heap sort are work
$this->heap_sort($arr, $tail + 1);
}
else
{
//When executed of quick sort
$pivot = $this->find_pivot($arr, $front, $front + (intval(($tail - $front) / 2)) + 1, $tail);
$this->swap_data($arr, $pivot, $tail);
$point = $this->partition($arr, $front, $tail);
$this->execute_introsort($arr, $front, $point - 1, $deep - 1);
$this->execute_introsort($arr, $point + 1, $tail, $deep - 1);
}
}
//Handling the request of introsort
public function introsort( & $arr, $size)
{
$deep = ((2 * floor(log($size) / log(2))));
$this->execute_introsort($arr, 0, $size - 1, $deep);
}
}
function main()
{
$obj = new MySort();
//Define an array of integers
$arr = array(11, 8, 3, 8, 12, -1, -3, 1, 4, 7, 5);
//Get the size
$size = count($arr);;
echo "\n Befre Sort :\n";
$obj->display($arr, $size);
//Sort element
$obj->introsort($arr, $size);
echo "\n After Sort :\n";
$obj->display($arr, $size);
$arr1 = array(9, -3, 5, 1, 7, 9, 3, 4, 5, 2, 4, 7, 8, -4, 6, 34, 43, 2, 7, 8, 11, 12, 9, -6, 2);
//Get the size
$size = count($arr1);
echo "\n Before Sort :\n";
$obj->display($arr1, $size);
//Sort element
$obj->introsort($arr1, $size);
echo "\n After Sort :\n";
$obj->display($arr1, $size);
}
main();Output
Befre Sort :
11 8 3 8 12 -1 -3 1 4 7 5
After Sort :
-3 -1 1 3 4 5 7 8 8 11 12
Before Sort :
9 -3 5 1 7 9 3 4 5 2 4 7 8 -4 6 34 43 2 7 8 11 12 9 -6 2
After Sort :
-6 -4 -3 1 2 2 2 3 4 4 5 5 6 7 7 7 8 8 9 9 9 11 12 34 43/*
Node Js Program
Sort array elements by using introsort
*/
class MySort
{
//Function which is display arr elements
display(arr, size)
{
for (var i = 0; i < size; ++i)
{
process.stdout.write(" " + arr[i]);
}
process.stdout.write("\n");
}
// Swapping the array elements in given location
swap_data(arr, first, second)
{
var temp = arr[first];
arr[first] = arr[second];
arr[second] = temp;
}
// Perform the insertion sort in given array
insertion_sort(arr, size)
{
var i = 0;
var j = 0;
for (i = 0; i < size - 1; ++i)
{
j = i + 1;
while (j > 0 && arr[j - 1] > arr[j])
{
//Swap array element
this.swap_data(arr, j, j - 1);
j--;
}
}
}
partition(arr, low, high)
{
//Set the high index element to its proper sorted position
var pv = arr[high];
var i = low - 1;
for (var j = low; j < high; ++j)
{
if (arr[j] < pv)
{
i++;
this.swap_data(arr, i, j);
}
}
//set the high index value to its sorted position
this.swap_data(arr, i + 1, high);
//returns the next sorting element location
return i + 1;
}
//Perform the quick sort in given array
quick_sort(arr, low, high)
{
if (low < high)
{
//Get the pivot element
var pv = this.partition(arr, low, high);
this.quick_sort(arr, low, pv - 1);
this.quick_sort(arr, pv + 1, high);
}
}
find_pivot(arr, a, b, c)
{
if (arr[a] < arr[b] && arr[b] < arr[c])
{
return b;
}
else if (arr[c] <= arr[b] && arr[b] <= arr[a])
{
return b;
}
else if (arr[b] < arr[c] && arr[c] <= arr[a])
{
return c;
}
else if (arr[a] < arr[c] && arr[c] <= arr[b])
{
return c;
}
else if (arr[b] <= arr[a] && arr[a] < arr[c])
{
return a;
}
else
{
return a;
}
}
compare(arr, left, right, root, size)
{
var location = -1;
if (left < size && arr[left] > arr[root])
{
if (right < size && arr[right] > arr[left])
{
this.swap_data(arr, right, root);
location = right;
}
else
{
this.swap_data(arr, left, root);
location = left;
}
}
else if (right < size && arr[right] > arr[root])
{
this.swap_data(arr, right, root);
location = right;
}
return location;
}
//Perform the operation of heap sort
heap(arr, size, root)
{
var left;
var right;
while (root != -1)
{
left = 2 * root + 1;
right = 2 * root + 2;
root = this.compare(arr, left, right, root, size);
}
}
//Sort array element using heap sort
heap_sort(arr, size)
{
for (var i = (parseInt(size / 2)) - 1; i >= 0; i--)
{
this.heap(arr, size, i);
}
for (var i = size - 1; i >= 0; i--)
{
this.swap_data(arr, 0, i);
this.heap(arr, i, 0);
}
}
//Perform the introsort in given array
execute_introsort(arr, front, tail, deep)
{
var size = tail - front;
if (size < 16)
{
this.insertion_sort(arr, tail + 1);
}
else if (deep == 0)
{
//when heap sort are work
this.heap_sort(arr, tail + 1);
}
else
{
//When executed of quick sort
var pivot = this.find_pivot(arr, front, front + (parseInt((tail - front) / 2)) + 1, tail);
this.swap_data(arr, pivot, tail);
var point = this.partition(arr, front, tail);
this.execute_introsort(arr, front, point - 1, deep - 1);
this.execute_introsort(arr, point + 1, tail, deep - 1);
}
}
//Handling the request of introsort
introsort(arr, size)
{
var deep = ((2 * Math.floor(Math.log(size) / Math.log(2))));
this.execute_introsort(arr, 0, size - 1, deep);
}
}
function main()
{
var obj = new MySort();
//Define an array of integers
var arr = [11, 8, 3, 8, 12, -1, -3, 1, 4, 7, 5];
//Get the size
var size = arr.length;;
process.stdout.write("\n Befre Sort :\n");
obj.display(arr, size);
//Sort element
obj.introsort(arr, size);
process.stdout.write("\n After Sort :\n");
obj.display(arr, size);
var arr1 = [9, -3, 5, 1, 7, 9, 3, 4, 5, 2, 4, 7, 8, -4, 6, 34, 43, 2, 7, 8, 11, 12, 9, -6, 2];
//Get the size
size = arr1.length;
process.stdout.write("\n Before Sort :\n");
obj.display(arr1, size);
//Sort element
obj.introsort(arr1, size);
process.stdout.write("\n After Sort :\n");
obj.display(arr1, size);
}
main();Output
Befre Sort :
11 8 3 8 12 -1 -3 1 4 7 5
After Sort :
-3 -1 1 3 4 5 7 8 8 11 12
Before Sort :
9 -3 5 1 7 9 3 4 5 2 4 7 8 -4 6 34 43 2 7 8 11 12 9 -6 2
After Sort :
-6 -4 -3 1 2 2 2 3 4 4 5 5 6 7 7 7 8 8 9 9 9 11 12 34 43import math
#
# Python 3 Program
# Sort array elements by using introsort
class MySort :
# Function which is display arr elements
def display(self, arr, size) :
i = 0
while (i < size) :
print(" ", arr[i], end = "")
i += 1
print("\n", end = "")
# Swapping the array elements in given location
def swap_data(self, arr, first, second) :
temp = arr[first]
arr[first] = arr[second]
arr[second] = temp
# Perform the insertion sort in given array
def insertion_sort(self, arr, size) :
i = 0
j = 0
while (i < size - 1) :
j = i + 1
while (j > 0 and arr[j - 1] > arr[j]) :
# Swap array element
self.swap_data(arr, j, j - 1)
j -= 1
i += 1
def partition(self, arr, low, high) :
# Set the high index element to its proper sorted position
pv = arr[high]
i = low - 1
j = low
while (j < high) :
if (arr[j] < pv) :
i += 1
self.swap_data(arr, i, j)
j += 1
# set the high index value to its sorted position
self.swap_data(arr, i + 1, high)
# returns the next sorting element location
return i + 1
# Perform the quick sort in given array
def quick_sort(self, arr, low, high) :
if (low < high) :
# Get the pivot element
pv = self.partition(arr, low, high)
self.quick_sort(arr, low, pv - 1)
self.quick_sort(arr, pv + 1, high)
def find_pivot(self, arr, a, b, c) :
if (arr[a] < arr[b] and arr[b] < arr[c]) :
return b
elif(arr[c] <= arr[b] and arr[b] <= arr[a]) :
return b
elif(arr[b] < arr[c] and arr[c] <= arr[a]) :
return c
elif(arr[a] < arr[c] and arr[c] <= arr[b]) :
return c
elif(arr[b] <= arr[a] and arr[a] < arr[c]) :
return a
else :
return a
def compare(self, arr, left, right, root, size) :
location = -1
if (left < size and arr[left] > arr[root]) :
if (right < size and arr[right] > arr[left]) :
self.swap_data(arr, right, root)
location = right
else :
self.swap_data(arr, left, root)
location = left
elif(right < size and arr[right] > arr[root]) :
self.swap_data(arr, right, root)
location = right
return location
# Perform the operation of heap sort
def heap(self, arr, size, root) :
left
right
while (root != -1) :
left = 2 * root + 1
right = 2 * root + 2
root = self.compare(arr, left, right, root, size)
# Sort array element using heap sort
def heap_sort(self, arr, size) :
i = (int(size / 2)) - 1
while (i >= 0) :
self.heap(arr, size, i)
i -= 1
i = size - 1
while (i >= 0) :
self.swap_data(arr, 0, i)
self.heap(arr, i, 0)
i -= 1
# Perform the introsort in given array
def execute_introsort(self, arr, front, tail, deep) :
size = tail - front
if (size < 16) :
self.insertion_sort(arr, tail + 1)
elif(deep == 0) :
# when heap sort are work
self.heap_sort(arr, tail + 1)
else :
# When executed of quick sort
pivot = self.find_pivot(arr, front, front + (int((tail - front) / 2)) + 1, tail)
self.swap_data(arr, pivot, tail)
point = self.partition(arr, front, tail)
self.execute_introsort(arr, front, point - 1, deep - 1)
self.execute_introsort(arr, point + 1, tail, deep - 1)
# Handling the request of introsort
def introsort(self, arr, size) :
deep = ((2 * math.floor(int(math.log(size) / math.log(2)))))
self.execute_introsort(arr, 0, size - 1, deep)
def main() :
obj = MySort()
# Define an array of integers
arr = [11, 8, 3, 8, 12, -1, -3, 1, 4, 7, 5]
# Get the size
size = len(arr)
print("\n Befre Sort :\n", end = "")
obj.display(arr, size)
# Sort element
obj.introsort(arr, size)
print("\n After Sort :\n", end = "")
obj.display(arr, size)
arr1 = [9, -3, 5, 1, 7, 9, 3, 4, 5, 2, 4, 7, 8, -4, 6, 34, 43, 2, 7, 8, 11, 12, 9, -6, 2]
# Get the size
size = len(arr1)
print("\n Before Sort :\n", end = "")
obj.display(arr1, size)
# Sort element
obj.introsort(arr1, size)
print("\n After Sort :\n", end = "")
obj.display(arr1, size)
if __name__ == "__main__": main()Output
Befre Sort :
11 8 3 8 12 -1 -3 1 4 7 5
After Sort :
-3 -1 1 3 4 5 7 8 8 11 12
Before Sort :
9 -3 5 1 7 9 3 4 5 2 4 7 8 -4 6 34 43 2 7 8 11 12 9 -6 2
After Sort :
-6 -4 -3 1 2 2 2 3 4 4 5 5 6 7 7 7 8 8 9 9 9 11 12 34 43# Ruby Program
# Sort array elements by using introsort
class MySort
# Function which is display arr elements
def display(arr, size)
i = 0
while (i < size)
print(" ", arr[i])
i += 1
end
print("\n")
end
# Swapping the array elements in given location
def swap_data(arr, first, second)
temp = arr[first]
arr[first] = arr[second]
arr[second] = temp
end
# Perform the insertion sort in given array
def insertion_sort(arr, size)
i = 0
j = 0
while (i < size - 1)
j = i + 1
while (j > 0 && arr[j - 1] > arr[j])
# Swap array element
self.swap_data(arr, j, j - 1)
j -= 1
end
i += 1
end
end
def partition(arr, low, high)
# Set the high index element to its proper sorted position
pv = arr[high]
i = low - 1
j = low
while (j < high)
if (arr[j] < pv)
i += 1
self.swap_data(arr, i, j)
end
j += 1
end
# set the high index value to its sorted position
self.swap_data(arr, i + 1, high)
# returns the next sorting element location
return i + 1
end
# Perform the quick sort in given array
def quick_sort(arr, low, high)
if (low < high)
# Get the pivot element
pv = self.partition(arr, low, high)
self.quick_sort(arr, low, pv - 1)
self.quick_sort(arr, pv + 1, high)
end
end
def find_pivot(arr, a, b, c)
if (arr[a] < arr[b] && arr[b] < arr[c])
return b
elsif(arr[c] <= arr[b] && arr[b] <= arr[a])
return b
elsif(arr[b] < arr[c] && arr[c] <= arr[a])
return c
elsif(arr[a] < arr[c] && arr[c] <= arr[b])
return c
elsif(arr[b] <= arr[a] && arr[a] < arr[c])
return a
else
return a
end
end
def compare(arr, left, right, root, size)
location = -1
if (left < size && arr[left] > arr[root])
if (right < size && arr[right] > arr[left])
self.swap_data(arr, right, root)
location = right
else
self.swap_data(arr, left, root)
location = left
end
elsif(right < size && arr[right] > arr[root])
self.swap_data(arr, right, root)
location = right
end
return location
end
# Perform the operation of heap sort
def heap(arr, size, root)
left
right
while (root != -1)
left = 2 * root + 1
right = 2 * root + 2
root = self.compare(arr, left, right, root, size)
end
end
# Sort array element using heap sort
def heap_sort(arr, size)
i = (size / 2) - 1
while (i >= 0)
self.heap(arr, size, i)
i -= 1
end
i = size - 1
while (i >= 0)
self.swap_data(arr, 0, i)
self.heap(arr, i, 0)
i -= 1
end
end
# Perform the introsort in given array
def execute_introsort(arr, front, tail, deep)
size = tail - front
if (size < 16)
self.insertion_sort(arr, tail + 1)
elsif(deep == 0)
# when heap sort are work
self.heap_sort(arr, tail + 1)
else
# When executed of quick sort
pivot = self.find_pivot(arr, front, front + ((tail - front) / 2) + 1, tail)
self.swap_data(arr, pivot, tail)
point = self.partition(arr, front, tail)
self.execute_introsort(arr, front, point - 1, deep - 1)
self.execute_introsort(arr, point + 1, tail, deep - 1)
end
end
# Handling the request of introsort
def introsort(arr, size)
deep = (2 * (Math.log(size) / Math.log(2)).floor).to_i
self.execute_introsort(arr, 0, size - 1, deep)
end
end
def main()
obj = MySort.new()
# Define an array of integers
arr = [11, 8, 3, 8, 12, -1, -3, 1, 4, 7, 5]
# Get the size
size = arr.length
print("\n Befre Sort :\n")
obj.display(arr, size)
# Sort element
obj.introsort(arr, size)
print("\n After Sort :\n")
obj.display(arr, size)
arr1 = [9, -3, 5, 1, 7, 9, 3, 4, 5, 2, 4, 7, 8, -4, 6, 34, 43, 2, 7, 8, 11, 12, 9, -6, 2]
# Get the size
size = arr1.length
print("\n Before Sort :\n")
obj.display(arr1, size)
# Sort element
obj.introsort(arr1, size)
print("\n After Sort :\n")
obj.display(arr1, size)
end
main()Output
Befre Sort :
11 8 3 8 12 -1 -3 1 4 7 5
After Sort :
-3 -1 1 3 4 5 7 8 8 11 12
Before Sort :
9 -3 5 1 7 9 3 4 5 2 4 7 8 -4 6 34 43 2 7 8 11 12 9 -6 2
After Sort :
-6 -4 -3 1 2 2 2 3 4 4 5 5 6 7 7 7 8 8 9 9 9 11 12 34 43
/*
Scala Program
Sort array elements by using introsort
*/
class MySort
{
//Function which is display arr elements
def display(arr: Array[Int], size: Int): Unit = {
var i: Int = 0;
while (i < size)
{
print(" " + arr(i));
i += 1;
}
print("\n");
}
// Swapping the array elements in given location
def swap_data(arr: Array[Int], first: Int, second: Int): Unit = {
var temp: Int = arr(first);
arr(first) = arr(second);
arr(second) = temp;
}
// Perform the insertion sort in given array
def insertion_sort(arr: Array[Int], size: Int): Unit = {
var i: Int = 0;
var j: Int = 0;
while (i < size - 1)
{
j = i + 1;
while (j > 0 && arr(j - 1) > arr(j))
{
//Swap array element
swap_data(arr, j, j - 1);
j -= 1;
}
i += 1;
}
}
def partition(arr: Array[Int], low: Int, high: Int): Int = {
//Set the high index element to its proper sorted position
var pv: Int = arr(high);
var i: Int = low - 1;
var j: Int = low;
while (j < high)
{
if (arr(j) < pv)
{
i += 1;
swap_data(arr, i, j);
}
j += 1;
}
//set the high index value to its sorted position
swap_data(arr, i + 1, high);
//returns the next sorting element location
return i + 1;
}
//Perform the quick sort in given array
def quick_sort(arr: Array[Int], low: Int, high: Int): Unit = {
if (low < high)
{
//Get the pivot element
var pv: Int = partition(arr, low, high);
quick_sort(arr, low, pv - 1);
quick_sort(arr, pv + 1, high);
}
}
def find_pivot(arr: Array[Int], a: Int, b: Int, c: Int): Int = {
if (arr(a) < arr(b) && arr(b) < arr(c))
{
return b;
}
else if (arr(c) <= arr(b) && arr(b) <= arr(a))
{
return b;
}
else if (arr(b) < arr(c) && arr(c) <= arr(a))
{
return c;
}
else if (arr(a) < arr(c) && arr(c) <= arr(b))
{
return c;
}
else if (arr(b) <= arr(a) && arr(a) < arr(c))
{
return a;
}
else
{
return a;
}
}
def compare(arr: Array[Int], left: Int, right: Int, root: Int, size: Int): Int = {
var location: Int = -1;
if (left < size && arr(left) > arr(root))
{
if (right < size && arr(right) > arr(left))
{
swap_data(arr, right, root);
location = right;
}
else
{
swap_data(arr, left, root);
location = left;
}
}
else if (right < size && arr(right) > arr(root))
{
swap_data(arr, right, root);
location = right;
}
return location;
}
//Perform the operation of heap sort
def heap(arr: Array[Int], size: Int, root: Int): Unit = {
var left: Int = 0;
var right: Int = 0;
var location = root;
while (location != -1)
{
left = 2 * location + 1;
right = 2 * location + 2;
location = compare(arr, left, right, location, size);
}
}
//Sort array element using heap sort
def heap_sort(arr: Array[Int], size: Int): Unit = {
var i: Int = ((size / 2).toInt) - 1;
while (i >= 0)
{
heap(arr, size, i);
i -= 1;
}
i = size - 1;
while (i >= 0)
{
swap_data(arr, 0, i);
heap(arr, i, 0);
i -= 1;
}
}
//Perform the introsort in given array
def execute_introsort(arr: Array[Int], front: Int, tail: Int, deep: Int): Unit = {
var size: Int = tail - front;
if (size < 16)
{
insertion_sort(arr, tail + 1);
}
else if (deep == 0)
{
//when heap sort are work
heap_sort(arr, tail + 1);
}
else
{
//When executed of quick sort
var pivot: Int = find_pivot(arr, front, front + (((tail - front) / 2).toInt) + 1, tail);
swap_data(arr, pivot, tail);
var point: Int = partition(arr, front, tail);
execute_introsort(arr, front, point - 1, deep - 1);
execute_introsort(arr, point + 1, tail, deep - 1);
}
}
//Handling the request of introsort
def introsort(arr: Array[Int], size: Int): Unit = {
val deep : Int = (2 * Math.floor(Math.log(size) / Math.log(2))).toInt;
execute_introsort(arr, 0, size - 1, deep);
}
}
object Main
{
def main(args: Array[String]): Unit = {
var obj: MySort = new MySort();
//Define an array of integers
var arr: Array[Int] = Array(11, 8, 3, 8, 12, -1, -3, 1, 4, 7, 5);
//Get the size
var size: Int = arr.length;
print("\n Befre Sort :\n");
obj.display(arr, size);
//Sort element
obj.introsort(arr, size);
print("\n After Sort :\n");
obj.display(arr, size);
var arr1: Array[Int] = Array(9, -3, 5, 1, 7, 9, 3, 4, 5, 2, 4, 7, 8, -4, 6, 34, 43, 2, 7, 8, 11, 12, 9, -6, 2);
//Get the size
size = arr1.length;
print("\n Before Sort :\n");
obj.display(arr1, size);
//Sort element
obj.introsort(arr1, size);
print("\n After Sort :\n");
obj.display(arr1, size);
}
}Output
Befre Sort :
11 8 3 8 12 -1 -3 1 4 7 5
After Sort :
-3 -1 1 3 4 5 7 8 8 11 12
Before Sort :
9 -3 5 1 7 9 3 4 5 2 4 7 8 -4 6 34 43 2 7 8 11 12 9 -6 2
After Sort :
-6 -4 -3 1 2 2 2 3 4 4 5 5 6 7 7 7 8 8 9 9 9 11 12 34 43import Foundation
/*
Swift Program
Sort array elements by using introsort
*/
class MySort
{
//Function which is display arr elements
func display(_ arr: [Int], _ size: Int)
{
var i: Int = 0;
while (i < size)
{
print(" ", arr[i], terminator: "");
i += 1;
}
print(terminator: "\n");
}
// Swapping the array elements in given location
func swap_data(_ arr: inout[Int], _ first: Int, _ second: Int)
{
let temp: Int = arr[first];
arr[first] = arr[second];
arr[second] = temp;
}
// Perform the insertion sort in given array
func insertion_sort(_ arr:inout [Int], _ size: Int)
{
var i: Int = 0;
var j: Int = 0;
while (i < size - 1)
{
j = i + 1;
while (j > 0 && arr[j - 1] > arr[j])
{
//Swap array element
self.swap_data(&arr, j, j - 1);
j -= 1;
}
i += 1;
}
}
func partition(_ arr: inout[Int], _ low: Int, _ high: Int) -> Int
{
//Set the high index element to its proper sorted position
let pv: Int = arr[high];
var i: Int = low - 1;
var j: Int = low;
while (j < high)
{
if (arr[j] < pv)
{
i += 1;
self.swap_data(&arr, i, j);
}
j += 1;
}
//set the high index value to its sorted position
self.swap_data(&arr, i + 1, high);
//returns the next sorting element location
return i + 1;
}
//Perform the quick sort in given array
func quick_sort(_ arr: inout[Int], _ low: Int, _ high: Int)
{
if (low < high)
{
//Get the pivot element
let pv: Int = self.partition(&arr, low, high);
self.quick_sort(&arr, low, pv - 1);
self.quick_sort(&arr, pv + 1, high);
}
}
func find_pivot(_ arr: [Int], _ a: Int, _ b: Int, _ c: Int) -> Int
{
if (arr[a] < arr[b] && arr[b] < arr[c])
{
return b;
}
else if (arr[c] <= arr[b] && arr[b] <= arr[a])
{
return b;
}
else if (arr[b] < arr[c] && arr[c] <= arr[a])
{
return c;
}
else if (arr[a] < arr[c] && arr[c] <= arr[b])
{
return c;
}
else if (arr[b] <= arr[a] && arr[a] < arr[c])
{
return a;
}
else
{
return a;
}
}
func compare(_ arr: inout[Int], _ left: Int, _ right: Int, _ root: Int, _ size: Int) -> Int
{
var location: Int = -1;
if (left < size && arr[left] > arr[root])
{
if (right < size && arr[right] > arr[left])
{
self.swap_data(&arr, right, root);
location = right;
}
else
{
self.swap_data(&arr, left, root);
location = left;
}
}
else if (right < size && arr[right] > arr[root])
{
self.swap_data(&arr, right, root);
location = right;
}
return location;
}
//Perform the operation of heap sort
func heap(_ arr: inout[Int], _ size: Int, _ root: Int)
{
var left: Int;
var right: Int;
var location : Int = root;
while (location != -1)
{
left = 2 * location + 1;
right = 2 * location + 2;
location = self.compare(&arr, left, right, location, size);
}
}
//Sort array element using heap sort
func heap_sort(_ arr: inout[Int], _ size: Int)
{
var i: Int = (size / 2) - 1;
while (i >= 0)
{
self.heap(&arr, size, i);
i -= 1;
}
i = size - 1;
while (i >= 0)
{
self.swap_data(&arr, 0, i);
self.heap(&arr, i, 0);
i -= 1;
}
}
//Perform the introsort in given array
func execute_introsort(_ arr: inout [Int], _ front: Int, _ tail: Int, _ deep: Int)
{
let size: Int = tail - front;
if (size < 16)
{
self.insertion_sort(&arr, tail + 1);
}
else if (deep == 0)
{
//when heap sort are work
self.heap_sort(&arr, tail + 1);
}
else
{
//When executed of quick sort
let pivot: Int = self.find_pivot(arr, front, front + ((tail - front) / 2) + 1, tail);
self.swap_data(&arr, pivot, tail);
let point: Int = self.partition(&arr, front, tail);
self.execute_introsort(&arr, front, point - 1, deep - 1);
self.execute_introsort(&arr, point + 1, tail, deep - 1);
}
}
//Handling the request of introsort
func introsort(_ arr: inout[Int], _ size: Int)
{
let deep: Int = Int(2 * log2(Double(size)));
self.execute_introsort(&arr, 0, size - 1, deep);
}
}
func main()
{
let obj: MySort = MySort();
//Define an array of integers
var arr: [Int] = [11, 8, 3, 8, 12, -1, -3, 1, 4, 7, 5];
//Get the size
var size: Int = arr.count;
print("\n Befre Sort :");
obj.display(arr, size);
//Sort element
obj.introsort(&arr, size);
print("\n After Sort :");
obj.display(arr, size);
var arr1: [Int] = [9, -3, 5, 1, 7, 9, 3, 4, 5, 2, 4, 7, 8, -4, 6, 34, 43, 2, 7, 8, 11, 12, 9, -6, 2];
//Get the size
size = arr1.count;
print("\n Before Sort :");
obj.display(arr1, size);
//Sort element
obj.introsort(&arr1, size);
print("\n After Sort :");
obj.display(arr1, size);
}
main();Output
Befre Sort :
11 8 3 8 12 -1 -3 1 4 7 5
After Sort :
-3 -1 1 3 4 5 7 8 8 11 12
Before Sort :
9 -3 5 1 7 9 3 4 5 2 4 7 8 -4 6 34 43 2 7 8 11 12 9 -6 2
After Sort :
-6 -4 -3 1 2 2 2 3 4 4 5 5 6 7 7 7 8 8 9 9 9 11 12 34 43
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment