Question

How to find the Kth smallest number in an unsorted array with Pascal

Answer 1

program KthSmallest;

const
  MaxSize = 128;

type
  IntArray = array[1..MaxSize] of Integer;

function FindKthSmallestNumber(var arr: IntArray; size, k: Integer): Integer;
var
  i, j, temp: Integer;
begin
  // Bubble sort
  for i := 1 to size - 1 do
    for j := 1 to size - i do
      if arr[j] > arr[j + 1] then
      begin
        temp := arr[j];
        arr[j] := arr[j + 1];
        arr[j + 1] := temp;
      end;

  FindKthSmallestNumber := arr[k];
end;

var
  arr: IntArray;
  size, k, result: Integer;
begin
  size := 7;
  arr[1] := 42;
  arr[2] := 90;
  arr[3] := 21;
  arr[4] := 30;
  arr[5] := 37;
  arr[6] := 81;
  arr[7] := 45;

  k := 3;
  result := FindKthSmallestNumber(arr, size, k);
  WriteLn(result);
end.



(*
run:

37

*)

 

70+ SQL courses for beginners and professionals

Answer 2

program KthSmallestQuickselect;
 
{
  This program demonstrates how to find the Kth smallest number
  in an unsorted array using the Quickselect algorithm.
 
  Quickselect is efficient because it avoids fully sorting the array.
  Average time complexity: O(n).
}
 
type
  TIntArray = array of Integer;
 
{---------------------------------------------------------------
  Swaps two elements in the array
---------------------------------------------------------------}
procedure Swap(var arr: TIntArray; i, j: Integer);
var
  temp: Integer;
begin
  temp := arr[i];
  arr[i] := arr[j];
  arr[j] := temp;
end;
 
{---------------------------------------------------------------
  Partitions the array around a pivot:
  - Values smaller than the pivot move left
  - Values larger move right
  Returns the pivot's final index.
---------------------------------------------------------------}
function Partition(var arr: TIntArray; left, right: Integer): Integer;
var
  pivotValue: Integer;
  storeIndex: Integer;
  i: Integer;
begin
  pivotValue := arr[right];
  storeIndex := left;
 
  for i := left to right - 1 do
  begin
    if arr[i] < pivotValue then
    begin
      Swap(arr, i, storeIndex);
      Inc(storeIndex);
    end;
  end;
 
  Swap(arr, storeIndex, right);
  Partition := storeIndex;
end;
 
{---------------------------------------------------------------
  Quickselect:
  Repeatedly partitions until the pivot lands on the desired index.
---------------------------------------------------------------}
function QuickSelect(var arr: TIntArray; left, right, targetIndex: Integer): Integer;
var
  pivotIndex: Integer;
begin
  while True do
  begin
    pivotIndex := Partition(arr, left, right);
 
    if pivotIndex = targetIndex then
      Exit(arr[pivotIndex])
    else if targetIndex < pivotIndex then
      right := pivotIndex - 1
    else
      left := pivotIndex + 1;
  end;
end;
 
{---------------------------------------------------------------
  Finds the Kth smallest number.
  Works on a copy of the array to avoid modifying the original.
---------------------------------------------------------------}
function FindKthSmallest(const arr: TIntArray; k: Integer): Integer;
var
  data: TIntArray;
  targetIndex: Integer;
  i: Integer;
begin
  SetLength(data, Length(arr));
  for i := 0 to High(arr) do
    data[i] := arr[i];
 
  targetIndex := k - 1;  { Convert to zero-based index }
 
  FindKthSmallest := QuickSelect(data, 0, High(data), targetIndex);
end;
 
{---------------------------------------------------------------
  Main program
---------------------------------------------------------------}
var
  numbers: TIntArray;
  k: Integer;
  result: Integer;
begin
  numbers := TIntArray.Create(42, 90, 50, 30, 37, 21, 83, 45);
  k := 3;
 
  result := FindKthSmallest(numbers, k);
 
  WriteLn('The ', k, 'rd smallest number is: ', result);
end.
 
 
 
(*
run:
 
The 3rd smallest number is: 37
 
*)
 

 

70+ SQL courses for beginners and professionals