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