Sum of k smallest elements in array

Here given code implementation process.

//C Program
//Sum of k smallest elements in array
#include <stdio.h>

//Swap two element in array
void swap(int arr[],int first,int second)
{
  int temp=arr[first];
  arr[first]=arr[second];
  arr[second]=temp;
}

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;
}
void heap_sort(int arr[],int size,int root)
{
  int left  = 2*root+1;
  int right = 2*root+2;
 
  int next = compare(arr, left, right, root, size);
 
  if(next != -1)
  {
    heap_sort(arr,size,next);
  }
}
//Display Array elements
void print_data(int arr[],int size)
{
  printf("\n");
  for(int i = 0; i < size; i++)
  {
    printf("%3d",arr[i] );
  }
}
//Sort the array elements and calculate sum of given smallest numbers 
void k_smallest(int arr[],int size,int k)
{

  if(k > size)
  {
    return;
  }
  int auxiliary[size] , sum=0;

  for (int i = 0; i < size; ++i)
  {
    auxiliary[i]=arr[i];
  }

  //Sort array elements
  for (int i = (size/2)-1; i >= 0; i--)
  {
    heap_sort(auxiliary,size,i);
  }


  for (int i = size-1; i >= 0; i--)
  {
    swap(auxiliary, 0, i);
    heap_sort(auxiliary, i, 0);
  }
  printf("\n  Sum of %d smallest element is : ",k);

  for (int i = 0; i < k; ++i)
  {
    sum += auxiliary[i];
  
  }
  printf("  %d \n",sum );

}
 int main()

 {
  //Define the array elements
  int arr[] = {6,5,4,16,1,8,9, 3, 8, 21, 11, 12 ,5};

  //Get the size of array
  int size = sizeof(arr)/sizeof(arr[0]);

  print_data(arr,size);

  int k = 4;

  k_smallest(arr,size,k);
 
  return 0;
}

Output

  6  5  4 16  1  8  9  3  8 21 11 12  5
  Sum of 4 smallest element is :   13
/*
  C++ Program
  Sum of k smallest elements in array
*/
#include<iostream>

using namespace std;


class MyHeap {
	public:

    //Swap two element in array
    void swap(int arr[], int first, int second) {
      int temp = arr[first];
      arr[first] = arr[second];
      arr[second] = temp;
    }
	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;
	}
	void heap_sort(int arr[], int size, int root) {
		int left = 2 *root + 1;
		int right = 2 *root + 2;
		int next = this->compare(arr, left, right, root, size);
		if (next != -1) {
			this->heap_sort(arr, size, next);
		}
	}
	//Display Array elements
	void print_data(int arr[], int size) {
		cout << "\n";
		for (int i = 0; i < size; i++) {
			cout << " " << arr[i];
		}
	}
	//Sort the array elements and calculate sum of given smallest numbers 
	void k_smallest(int arr[], int size, int k) {
		if (k > size) {
			return;
		}
		int auxiliary[size];
		int sum = 0;
		for (int i = 0; i < size; ++i) {
			auxiliary[i] = arr[i];
		}
		//Sort array elements

		for (int i = (size / 2) - 1; i >= 0; i--) {
			this->heap_sort(auxiliary, size, i);
		}
		for (int i = size - 1; i >= 0; i--) {
			this->swap(auxiliary, 0, i);
			this->heap_sort(auxiliary, i, 0);
		}
		cout << "\n Sum of " << k << " smallest element is : ";
		for (int i = 0; i < k; ++i) {
			sum += auxiliary[i];
		}
		cout << " " << sum << "\n";
	}
};
int main() {
	MyHeap obj = MyHeap();
	int arr[] = {
		6,
		5,
		4,
		16,
		1,
		8,
		9,
		3,
		8,
		21,
		11,
		12,
		5
	};
	int k = 4;
	int size = sizeof(arr) / sizeof(arr[0]);
	obj.print_data(arr, size);
	obj.k_smallest(arr, size, k);
	return 0;
}

Output

 6 5 4 16 1 8 9 3 8 21 11 12 5
 Sum of 4 smallest element is :  13
/*
  Java Program
  Sum of k smallest elements in array
*/

public class MyHeap 
{ 
  //Swap two element in array
  public void swap(int []arr,int first,int second)
  {
    int temp=arr[first];
    arr[first]=arr[second];
    arr[second]=temp;
  }

  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;
  }
  public void heap_sort(int []arr,int size,int root)
  {
    int left  = 2*root+1;
    int right = 2*root+2;
   
    int next = compare(arr, left, right, root, size);
   
    if(next != -1)
    {
      heap_sort(arr,size,next);
    }
  }
  //Display Array elements
  public void print_data(int []arr,int size)
  {
    System.out.print("\n");
    for(int i = 0; i < size; i++)
    {
      System.out.print(" "+arr[i] );
    }
  }
  //Sort the array elements and calculate sum of given smallest numbers 
  public void k_smallest(int []arr,int size,int k)
  {

    if(k > size)
    {
      return;
    }
    int []auxiliary= new int[size] ;
    int sum=0;

    for (int i = 0; i < size; ++i)
    {
      auxiliary[i]=arr[i];
    }

    //Sort array elements
    for (int i = (size/2)-1; i >= 0; i--)
    {
      heap_sort(auxiliary,size,i);
    }


    for (int i = size-1; i >= 0; i--)
    {
      swap(auxiliary, 0, i);
      heap_sort(auxiliary, i, 0);
    }
    System.out.print("\n Sum of "+k+" smallest element is : ");

    for (int i = 0; i < k; ++i)
    {
      sum += auxiliary[i];
    
    }
    System.out.print(" "+sum+"\n" );

  }
  public static void main(String[] args) {
    MyHeap obj = new MyHeap();
    //Given array elements
    int []arr = {6,5,4,16,1,8,9, 3, 8, 21, 11, 12 ,5}; 
   
    int k = 4;

    int size = arr.length;

    obj.print_data(arr,size);

    

    obj.k_smallest(arr,size,k);

  }
}

Output

 6 5 4 16 1 8 9 3 8 21 11 12 5
 Sum of 4 smallest element is :  13
/*
  C# Program
  Sum of k smallest elements in array
*/
using System;


public class MyHeap {
	//Swap two element in array
	public void swap(int[] arr, int first, int second) {
		int temp = arr[first];
		arr[first] = arr[second];
		arr[second] = temp;
	}
	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;
	}
	public void heap_sort(int[] arr, int size, int root) {
		int left = 2 * root + 1;
		int right = 2 * root + 2;
		int next = compare(arr, left, right, root, size);
		if (next != -1) {
			heap_sort(arr, size, next);
		}
	}
	//Display Array elements
	public void print_data(int[] arr, int size) {
		Console.Write("\n");
		for (int i = 0; i < size; i++) {
			Console.Write(" " + arr[i]);
		}
	}
	//Sort the array elements and calculate sum of given smallest numbers 
	public void k_smallest(int[] arr, int size, int k) {
		if (k > size) {
			return;
		}
		int[] auxiliary = new int[size];
		int sum = 0;
		for (int i = 0; i < size; ++i) {
			auxiliary[i] = arr[i];
		}
		//Sort array elements

		for (int i = (size / 2) - 1; i >= 0; i--) {
			heap_sort(auxiliary, size, i);
		}
		for (int i = size - 1; i >= 0; i--) {
			swap(auxiliary, 0, i);
			heap_sort(auxiliary, i, 0);
		}
		Console.Write("\n Sum of " + k + " smallest element is : ");
		for (int i = 0; i < k; ++i) {
			sum += auxiliary[i];
		}
		Console.Write(" " + sum + "\n");
	}
	public static void Main(String[] args) {
		MyHeap obj = new MyHeap();
		int[]
		//Given array elements
		arr = {
			6,
			5,
			4,
			16,
			1,
			8,
			9,
			3,
			8,
			21,
			11,
			12,
			5
		};
		int k = 4;
		int size = arr.Length;
		obj.print_data(arr, size);
		obj.k_smallest(arr, size, k);
	}
}

Output

 6 5 4 16 1 8 9 3 8 21 11 12 5
 Sum of 4 smallest element is :  13
<?php
/*
  Php Program
  Sum of k smallest elements in array
*/
class MyHeap {
	//Swap two element in array

	public 	function swap(&$arr, $first, $second) {
		$temp = $arr[$first];
		$arr[$first] = $arr[$second];
		$arr[$second] = $temp;
	}
	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;
	}
	public 	function heap_sort(&$arr, $size, $root) {
		$left = 2 *$root + 1;
		$right = 2 *$root + 2;
		$next = $this->compare($arr, $left, $right, $root, $size);
		if ($next != -1) {
			$this->heap_sort($arr, $size, $next);
		}
	}
	//Display Array elements

	public 	function print_data($arr, $size) {
		echo("\n");
		for ($i = 0; $i < $size; $i++) {
			echo(" ". $arr[$i]);
		}
	}
	//Sort the array elements and calculate sum of given smallest numbers 

	public 	function k_smallest($arr, $size, $k) {
		if ($k > $size) {
			return;
		}
		$auxiliary = array_fill(0, $size, 0);
		$sum = 0;
		for ($i = 0; $i < $size; ++$i) {
			$auxiliary[$i] = $arr[$i];
		}
		//Sort array elements

		for ($i = (intval($size / 2)) - 1; $i >= 0; $i--) {
			$this->heap_sort($auxiliary, $size, $i);
		}
		for ($i = $size - 1; $i >= 0; $i--) {
			$this->swap($auxiliary, 0, $i);
			$this->heap_sort($auxiliary, $i, 0);
		}
		echo("\n Sum of ". $k ." smallest element is : ");
		for ($i = 0; $i < $k; ++$i) {
			$sum += $auxiliary[$i];
		}
		echo(" ". $sum ."\n");
	}
}

function main() {
	$obj = new MyHeap();
	//Given array elements
	$arr = array(6, 5, 4, 16, 1, 8, 9, 3, 8, 21, 11, 12, 5);
	$k = 4;
	$size = count($arr);
	$obj->print_data($arr, $size);
	$obj->k_smallest($arr, $size, $k);

}
main();

Output

 6 5 4 16 1 8 9 3 8 21 11 12 5
 Sum of 4 smallest element is :  13
/*
  Node Js Program
  Sum of k smallest elements in array
*/
class MyHeap {
	//Swap two element in array
	swap(arr, first, second) {
		var temp = arr[first];
		arr[first] = arr[second];
		arr[second] = temp;
	}
	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;
	}
	heap_sort(arr, size, root) {
		var left = 2 *root + 1;
		var right = 2 *root + 2;
		var next = this.compare(arr, left, right, root, size);
		if (next != -1) {
			this.heap_sort(arr, size, next);
		}
	}

	//Display Array elements
	print_data(arr, size) {
		process.stdout.write("\n");
		for (var i = 0; i < size; i++) {
			process.stdout.write(" " + arr[i]);
		}
	}

	//Sort the array elements and calculate sum of given smallest numbers 
	k_smallest(arr, size, k) {
		if (k > size) {
			return;
		}
		var auxiliary = Array(size).fill(0);
		var sum = 0;
		for (var i = 0; i < size; ++i) {
			auxiliary[i] = arr[i];
		}

		//Sort array elements

		for (var i = (parseInt(size / 2)) - 1; i >= 0; i--) {
			this.heap_sort(auxiliary, size, i);
		}

		for (var i = size - 1; i >= 0; i--) {
			this.swap(auxiliary, 0, i);
			this.heap_sort(auxiliary, i, 0);
		}

		process.stdout.write("\n Sum of " + k + " smallest element is : ");
		for (var i = 0; i < k; ++i) {
			sum += auxiliary[i];
		}

		process.stdout.write(" " + sum + "\n");
	}
}

function main(args) {
	var obj = new MyHeap();
	//Given array elements
	var arr = [6, 5, 4, 16, 1, 8, 9, 3, 8, 21, 11, 12, 5];
	var k = 4;
	var size = arr.length;
	obj.print_data(arr, size);
	obj.k_smallest(arr, size, k);
}

main();

Output

 6 5 4 16 1 8 9 3 8 21 11 12 5
 Sum of 4 smallest element is :  13
# Python 3 Program
# Sum of k smallest elements in array
class MyHeap :
	# Swap two element in array
	def swap(self, arr, first, second) :
		temp = arr[first]
		arr[first] = arr[second]
		arr[second] = temp
	
	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
	
	def heap_sort(self, arr, size, root) :
		left = 2 * root + 1
		right = 2 * root + 2
		next = self.compare(arr, left, right, root, size)
		if (next != -1) :
			self.heap_sort(arr, size, next)
		
	
	# Display Array elements
	def print_data(self, arr, size) :
		print("\n", end = "")
		i = 0
		while (i < size) :
			print(" ", arr[i], end = "")
			i += 1
		
	
	# Sort the array elements and calculate sum of given smallest numbers 
	def k_smallest(self, arr, size, k) :
		if (k > size) :
			return
		
		auxiliary = [0] * size
		sum = 0
		i = 0
		while (i < size) :
			auxiliary[i] = arr[i]
			i += 1
		
		# Sort array elements
		i = (int(size / 2)) - 1
		while (i >= 0) :
			self.heap_sort(auxiliary, size, i)
			i -= 1
		
		i = size - 1
		while (i >= 0) :
			self.swap(auxiliary, 0, i)
			self.heap_sort(auxiliary, i, 0)
			i -= 1
		
		print("\n Sum of ", k ," smallest element is : ", end = "")
		i = 0
		while (i < k) :
			sum += auxiliary[i]
			i += 1
		
		print(" ", sum ,"\n", end = "")
	

def main() :
	obj = MyHeap()
	# Given array elements
	arr = [6, 5, 4, 16, 1, 8, 9, 3, 8, 21, 11, 12, 5]
	k = 4
	size = len(arr)
	obj.print_data(arr, size)
	obj.k_smallest(arr, size, k)


if __name__ == "__main__":
	main()

Output

  6  5  4  16  1  8  9  3  8  21  11  12  5
 Sum of  4  smallest element is :   13
# Ruby Program
# Sum of k smallest elements in array
class MyHeap 
	# Swap two element in array
	def swap(arr, first, second) 
		temp = arr[first]
		arr[first] = arr[second]
		arr[second] = temp
	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
	def heap_sort(arr, size, root) 
		left = 2 * root + 1
		right = 2 * root + 2
		next_node = self.compare(arr, left, right, root, size)
		if (next_node != -1) 
			self.heap_sort(arr, size, next_node)
		end
	end
	# Display Array elements
	def print_data(arr, size) 
		print("\n")
		i = 0
		while (i < size) 
			print(" ", arr[i])
			i += 1
		end
	end
	# Sort the array elements and calculate sum of given smallest numbers 
	def k_smallest(arr, size, k) 
		if (k > size) 
			return
		end
		auxiliary = Array.new(size, 0)
		sum = 0
		i = 0
		while (i < size) 
			auxiliary[i] = arr[i]
			i += 1
		end
		# Sort array elements
		i = (size / 2) - 1
		while (i >= 0) 
			self.heap_sort(auxiliary, size, i)
			i -= 1
		end
		i = size - 1
		while (i >= 0) 
			self.swap(auxiliary, 0, i)
			self.heap_sort(auxiliary, i, 0)
			i -= 1
		end
		print("\n Sum of ", k ," smallest element is  :")
		i = 0
		while (i < k) 
			sum += auxiliary[i]
			i += 1
		end
		print(" ", sum ,"\n")
	end
end
def main() 
	obj = MyHeap.new()
	# Given array elements
	arr = [6, 5, 4, 16, 1, 8, 9, 3, 8, 21, 11, 12, 5]
	k = 4
	size = arr.length
	obj.print_data(arr, size)
	obj.k_smallest(arr, size, k)
end
main()

Output

 6 5 4 16 1 8 9 3 8 21 11 12 5
 Sum of 4 smallest element is  : 13
/*
  Scala Program
  Sum of k smallest elements in array
*/
class MyHeap {
	//Swap two element in array
	def swap(arr: Array[Int], first: Int, second: Int): Unit = {
		val temp: Int = arr(first);
		arr(first) = arr(second);
		arr(second) = temp;
	}
	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;
	}
	def heap_sort(arr: Array[Int], size: Int, root: Int): Unit = {
		val left: Int = 2 * root + 1;
		val right: Int = 2 * root + 2;
		val next: Int = this.compare(arr, left, right, root, size);

		if (next != -1) {
			this.heap_sort(arr, size, next);
		}
	}
	//Display Array elements
	def print_data(arr: Array[Int], size: Int): Unit = {
		print("\n");
		var i: Int = 0;
		while (i < size) {
			print(" " + arr(i));
			i += 1;
		}
	}
	//Sort the array elements and calculate sum of given smallest numbers 
	def k_smallest(arr: Array[Int], size: Int, k: Int): Unit = {
		if (k > size) {
			return;
		}
		var auxiliary: Array[Int] = Array.fill[Int](size)(0);
        var sum: Int = 0;
        var i: Int = 0;
        while (i < size) {
            auxiliary(i) = arr(i);
            i += 1;
        }
        //Sort array elements
        i = ((size / 2).toInt) - 1;
        while (i >= 0) {
            this.heap_sort(auxiliary, size, i);
            i -= 1;
        }
        i = size - 1;
        while (i >= 0) {
            this.swap(auxiliary, 0, i);
            this.heap_sort(auxiliary, i, 0);
            i -= 1;
        }
        print("\n Sum of " + k + " smallest element is : ");
        i = 0;
        while (i < k) {
            sum += auxiliary(i);
            i += 1;
        }
        print(" " + sum + "\n");
    }
}
object Main {
	def main(args: Array[String]): Unit = {
		val obj: MyHeap = new MyHeap();

		//Given array elements
		val arr: Array[Int] = Array(6, 5, 4, 16, 1, 8, 9, 3, 8, 21, 11, 12, 5);
		val k: Int = 4;
		val size: Int = arr.length;
		obj.print_data(arr, size);
		obj.k_smallest(arr, size, k);
	}
}

Output

 6 5 4 16 1 8 9 3 8 21 11 12 5
 Sum of 4 smallest element is :  13
/*
  Swift Program
  Sum of k smallest elements in array
*/
class MyHeap {
	//Swap two element in array
	func swap(_ arr: inout [Int], _ first: Int, _ second: Int) {
		let temp: Int = arr[first];
		arr[first] = arr[second];
		arr[second] = temp;
	}
	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(&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;
	}
	func heap_sort(_ arr: inout [Int], _ size: Int, _ root: Int) {
		let left: Int = 2 * root + 1;
		let right: Int = 2 * root + 2;
		let next: Int = self.compare(&arr, left, right, root, size);
		if (next != -1) {
			self.heap_sort(&arr, size, next);
		}
	}
	//Display Array elements
	func print_data(_ arr: [Int], _ size: Int) {
		print("\n", terminator: "");
		var i: Int = 0;
		while (i < size) {
			print(" ", arr[i], terminator: "");
			i += 1;
		}
	}
	//Sort the array elements and calculate sum of given smallest numbers 
	func k_smallest(_ arr: [Int], _ size: Int, _ k: Int) {
		if (k > size) {
			return;
		}
		var auxiliary: [Int] = Array(repeating: 0, count: size);
        var sum: Int = 0;
        var i: Int = 0;
        while (i < size) {
            auxiliary[i] = arr[i];
            i += 1;
        }
        //Sort array elements
        i = (size / 2) - 1;
        while (i >= 0) {
            self.heap_sort(&auxiliary, size, i);
            i -= 1;
        }
        i = size - 1;
        while (i >= 0) {
            self.swap(&auxiliary, 0, i);
            self.heap_sort(&auxiliary, i, 0);
            i -= 1;
        }
        print("\n Sum of ", k ," smallest element is : ", terminator: "");
        i = 0;
        while (i < k) {
            sum += auxiliary[i];
            i += 1;
        }
        print(" ", sum ,"\n", terminator: "");
    }
}
func main() {
	let obj: MyHeap = MyHeap();
	//Given array elements
	let arr: [Int] = [6, 5, 4, 16, 1, 8, 9, 3, 8, 21, 11, 12, 5];
	let k: Int = 4;
	let size: Int = arr.count;
	obj.print_data(arr, size);
	obj.k_smallest(arr, size, k);
}
main();

Output

  6  5  4  16  1  8  9  3  8  21  11  12  5
 Sum of  4  smallest element is :   13


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







© 2021, kalkicode.com, All rights reserved