Iterative Heap Sort
Here given code implementation process.
//C Program
//Iterative Heap Sort
#include <stdio.h>
//Swap two element in array
void swap(int arr[],int first,int second)
{
int auxiliary=arr[first];
arr[first]=arr[second];
arr[second]=auxiliary;
}
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(arr,right,root);
location = right;
}
else
{
swap(arr,left,root);
location = left;
}
}
else if(right < size && arr[right] > arr[root])
{
swap(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(arr, 0, i);
heap(arr, i, 0);
}
}
void print_data(int arr[],int size)
{
for(int i = 0; i < size; i++)
{
printf(" %d",arr[i] );
}
printf("\n");
}
int main()
{
//Collection of unordered sorted array
int arr[] = {6, 8, 2, 2, 7, 1, 3, 8, 21, 11, 12 ,5};
//Get the size of array
int size = sizeof(arr)/sizeof(arr[0]);
printf(" Before Sort\n");
print_data(arr,size);
heap_sort(arr,size);
printf(" After Sort\n");
print_data(arr,size);
return 0;
}
Output
Before Sort
6 8 2 2 7 1 3 8 21 11 12 5
After Sort
1 2 2 3 5 6 7 8 8 11 12 21/*
C++ Program
Iterative Heap Sort
*/
#include<iostream>
using namespace std;
class MyHeap {
public:
//Swap two element in array
void swap(int arr[], int first, int second) {
int auxiliary = arr[first];
arr[first] = arr[second];
arr[second] = auxiliary;
}
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(arr, right, root);
location = right;
} else {
this->swap(arr, left, root);
location = left;
}
} else
if (right < size && arr[right] > arr[root]) {
this->swap(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(arr, 0, i);
this->heap(arr, i, 0);
}
}
void print_data(int arr[], int size) {
for (int i = 0; i < size; i++) {
cout << " " << arr[i];
}
cout << "\n";
}
};
int main() {
MyHeap obj = MyHeap();
int arr[] = {
6,
8,
2,
2,
7,
1,
3,
8,
21,
11,
12,
5
};
//Get the size of array
int size = sizeof(arr) / sizeof(arr[0]);
cout << " Before Sort\n";
obj.print_data(arr, size);
obj.heap_sort(arr, size);
cout << "\n After Sort\n";
obj.print_data(arr, size);
return 0;
}
Output
Before Sort
6 8 2 2 7 1 3 8 21 11 12 5
After Sort
1 2 2 3 5 6 7 8 8 11 12 21/*
Java Program
Iterative Heap Sort
*/
public class MyHeap {
//Swap two element in array
public void swap(int []arr,int first,int second)
{
int auxiliary=arr[first];
arr[first]=arr[second];
arr[second]=auxiliary;
}
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(arr,right,root);
location = right;
}
else
{
swap(arr,left,root);
location = left;
}
}
else if(right < size && arr[right] > arr[root])
{
swap(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(arr, 0, i);
heap(arr, i, 0);
}
}
public void print_data(int []arr,int size)
{
for(int i = 0; i < size; i++)
{
System.out.print(" "+arr[i] );
}
System.out.print("\n");
}
public static void main(String[] args) {
MyHeap obj = new MyHeap();
//Collection of unordered sorted array
int []arr = {6, 8, 2, 2, 7, 1, 3, 8, 21, 11, 12 ,5};
//Get the size of array
int size = arr.length;
System.out.print(" Before Sort\n");
obj.print_data(arr,size);
obj.heap_sort(arr,size);
System.out.print("\n After Sort\n");
obj.print_data(arr,size);
}
}
Output
Before Sort
6 8 2 2 7 1 3 8 21 11 12 5
After Sort
1 2 2 3 5 6 7 8 8 11 12 21/*
C# Program
Iterative Heap Sort
*/
using System;
public class MyHeap {
//Swap two element in array
public void swap(int[] arr, int first, int second) {
int auxiliary = arr[first];
arr[first] = arr[second];
arr[second] = auxiliary;
}
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(arr, right, root);
location = right;
} else {
swap(arr, left, root);
location = left;
}
} else
if (right < size && arr[right] > arr[root]) {
swap(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(arr, 0, i);
heap(arr, i, 0);
}
}
public void print_data(int[] arr, int size) {
for (int i = 0; i < size; i++) {
Console.Write(" " + arr[i]);
}
Console.Write("\n");
}
public static void Main(String[] args) {
MyHeap obj = new MyHeap();
int[]
//Collection of unordered sorted array
arr = {
6,
8,
2,
2,
7,
1,
3,
8,
21,
11,
12,
5
};
//Get the size of array
int size = arr.Length;
Console.Write(" Before Sort\n");
obj.print_data(arr, size);
obj.heap_sort(arr, size);
Console.Write("\n After Sort\n");
obj.print_data(arr, size);
}
}
Output
Before Sort
6 8 2 2 7 1 3 8 21 11 12 5
After Sort
1 2 2 3 5 6 7 8 8 11 12 21<?php
/*
Php Program
Iterative Heap Sort
*/
class MyHeap {
//Swap two element in array
public function swap(&$arr, $first, $second) {
$auxiliary = $arr[$first];
$arr[$first] = $arr[$second];
$arr[$second] = $auxiliary;
}
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($arr, $right, $root);
$location = $right;
} else {
$this->swap($arr, $left, $root);
$location = $left;
}
} else
if ($right < $size && $arr[$right] > $arr[$root]) {
$this->swap($arr, $right, $root);
$location = $right;
}
return $location;
}
//Perform the operation of heap sort
public function heap(&$arr, $size, $root) {
$left = 0;
$right = 0;
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($arr, 0, $i);
$this->heap($arr, $i, 0);
}
}
public function print_data($arr, $size) {
for ($i = 0; $i < $size; $i++) {
echo(" ". $arr[$i]);
}
echo("\n");
}
}
function main() {
$obj = new MyHeap();
//Collection of unordered sorted array
$arr = array(6, 8, 2, 2, 7, 1, 3, 8, 21, 11, 12, 5);
//Get the size of array
$size = count($arr);
echo(" Before Sort\n");
$obj->print_data($arr, $size);
$obj->heap_sort($arr, $size);
echo("\n After Sort\n");
$obj->print_data($arr, $size);
}
main();
Output
Before Sort
6 8 2 2 7 1 3 8 21 11 12 5
After Sort
1 2 2 3 5 6 7 8 8 11 12 21/*
Node Js Program
Iterative Heap Sort
*/
class MyHeap {
//Swap two element in array
swap(arr, first, second) {
var auxiliary = arr[first];
arr[first] = arr[second];
arr[second] = auxiliary;
}
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(arr, right, root);
location = right;
} else {
this.swap(arr, left, root);
location = left;
}
} else
if (right < size && arr[right] > arr[root]) {
this.swap(arr, right, root);
location = right;
}
return location;
}
//Perform the operation of heap sort
heap(arr, size, root) {
var left = 0;
var right = 0;
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(arr, 0, i);
this.heap(arr, i, 0);
}
}
print_data(arr, size) {
for (var i = 0; i < size; i++) {
process.stdout.write(" " + arr[i]);
}
process.stdout.write("\n");
}
}
function main(args) {
var obj = new MyHeap();
//Collection of unordered sorted array
var arr = [6, 8, 2, 2, 7, 1, 3, 8, 21, 11, 12, 5];
//Get the size of array
var size = arr.length;
process.stdout.write(" Before Sort\n");
obj.print_data(arr, size);
obj.heap_sort(arr, size);
process.stdout.write("\n After Sort\n");
obj.print_data(arr, size);
}
main();
Output
Before Sort
6 8 2 2 7 1 3 8 21 11 12 5
After Sort
1 2 2 3 5 6 7 8 8 11 12 21# Python 3 Program
# Iterative Heap Sort
class MyHeap :
# Swap two element in array
def swap(self, arr, first, second) :
auxiliary = arr[first]
arr[first] = arr[second]
arr[second] = auxiliary
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(arr, right, root)
location = right
else :
self.swap(arr, left, root)
location = left
elif (right < size and arr[right] > arr[root]) :
self.swap(arr, right, root)
location = right
return location
# Perform the operation of heap sort
def heap(self, arr, size, root) :
left = 0
right = 0
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(arr, 0, i)
self.heap(arr, i, 0)
i -= 1
def print_data(self, arr, size) :
i = 0
while (i < size) :
print(" ", arr[i], end = "")
i += 1
print("\n", end = "")
def main() :
obj = MyHeap()
arr = [6, 8, 2, 2, 7, 1, 3, 8, 21, 11, 12, 5]
size = len(arr)
print(" Before Sort\n", end = "")
obj.print_data(arr, size)
obj.heap_sort(arr, size)
print("\n After Sort\n", end = "")
obj.print_data(arr, size)
if __name__ == "__main__":
main()
Output
Before Sort
6 8 2 2 7 1 3 8 21 11 12 5
After Sort
1 2 2 3 5 6 7 8 8 11 12 21# Ruby Program
# Iterative Heap Sort
class MyHeap
# Swap two element in array
def swap(arr, first, second)
auxiliary = arr[first]
arr[first] = arr[second]
arr[second] = auxiliary
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(arr, right, root)
location = right
else
self.swap(arr, left, root)
location = left
end
elsif (right < size && arr[right] > arr[root])
self.swap(arr, right, root)
location = right
end
return location
end
# Perform the operation of heap sort
def heap(arr, size, root)
left = 0
right = 0
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(arr, 0, i)
self.heap(arr, i, 0)
i -= 1
end
end
def print_data(arr, size)
i = 0
while (i < size)
print(" ", arr[i])
i += 1
end
print("\n")
end
end
def main()
obj = MyHeap.new()
arr = [6, 8, 2, 2, 7, 1, 3, 8, 21, 11, 12, 5]
size = arr.length
print(" Before Sort\n")
obj.print_data(arr, size)
obj.heap_sort(arr, size)
print("\n After Sort\n")
obj.print_data(arr, size)
end
main()
Output
Before Sort
6 8 2 2 7 1 3 8 21 11 12 5
After Sort
1 2 2 3 5 6 7 8 8 11 12 21
/*
Scala Program
Iterative Heap Sort
*/
class MyHeap {
//Swap two element in array
def swap(arr: Array[Int], first: Int, second: Int): Unit = {
val auxiliary: Int = arr(first);
arr(first) = arr(second);
arr(second) = auxiliary;
}
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)) {
this.swap(arr, right, root);
location = right;
} else {
this.swap(arr, left, root);
location = left;
}
} else
if (right < size && arr(right) > arr(root)) {
this.swap(arr, right, root);
location = right;
}
return location;
}
//Perform the operation of heap sort
def heap(arr: Array[Int], size: Int, location : Int): Unit = {
var left: Int = 0;
var right: Int = 0;
var root : Int = location;
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
def heap_sort(arr: Array[Int], size: Int): Unit = {
var i: Int = ((size / 2).toInt) - 1;
while (i >= 0) {
this.heap(arr, size, i);
i -= 1;
}
i = size - 1;
while (i >= 0) {
this.swap(arr, 0, i);
this.heap(arr, i, 0);
i -= 1;
}
}
def print_data(arr: Array[Int], size: Int): Unit = {
var i: Int = 0;
while (i < size) {
print(" " + arr(i));
i += 1;
}
print("\n");
}
}
object Main {
def main(args: Array[String]): Unit = {
val obj: MyHeap = new MyHeap();
var arr: Array[Int] = Array(6, 8, 2, 2, 7, 1, 3, 8, 21, 11, 12, 5);
val size: Int = arr.length;
print(" Before Sort\n");
obj.print_data(arr, size);
obj.heap_sort(arr, size);
print("\n After Sort\n");
obj.print_data(arr, size);
}
}
Output
Before Sort
6 8 2 2 7 1 3 8 21 11 12 5
After Sort
1 2 2 3 5 6 7 8 8 11 12 21/*
Swift Program
Iterative Heap Sort
*/
class MyHeap {
//Swap two element in array
func swap(_ arr: inout[Int], _ first: Int, _ second: Int) {
let auxiliary = arr[first];
arr[first] = arr[second];
arr[second] = auxiliary;
}
func compare(_ arr: inout [Int], _ left: Int, _ right: Int, _ root: Int, _ size: Int) -> Int {
var location = -1;
if (left < size && arr[left] > arr[root]) {
if (right < size && arr[right] > arr[left]) {
self.swap(&arr, right, root);
location = right;
} else {
self.swap(&arr, left, root);
location = left;
}
} else
if (right < size && arr[right] > arr[root]) {
self.swap(&arr, right, root);
location = right;
}
return location;
}
//Perform the operation of heap sort
func heap(_ arr: inout [Int], _ size: Int, _ location: Int) {
var left = 0;
var right = 0;
var root = location;
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
func heap_sort(_ arr: inout [Int], _ size: Int) {
var i = (size / 2) - 1;
while (i >= 0) {
self.heap(&arr, size, i);
i -= 1;
}
i = size - 1;
while (i >= 0) {
self.swap(&arr, 0, i);
self.heap(&arr, i, 0);
i -= 1;
}
}
func print_data(_ arr: [Int], _ size: Int) {
var i = 0;
while (i < size) {
print(" ", arr[i], terminator: "");
i += 1;
}
print("\n", terminator: "");
}
}
func main() {
let obj = MyHeap();
var arr = [6, 8, 2, 2, 7, 1, 3, 8, 21, 11, 12, 5];
let size = arr.count;
print(" Before Sort\n", terminator: "");
obj.print_data(arr, size);
obj.heap_sort(&arr, size);
print("\n After Sort\n", terminator: "");
obj.print_data(arr, size);
}
main();
Output
Before Sort
6 8 2 2 7 1 3 8 21 11 12 5
After Sort
1 2 2 3 5 6 7 8 8 11 12 21
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