<commit_before><commit_msg>kth smallest in unsorted file o(n) time. if k=n/2 -> it's the median<commit_after>#include <iostream>
using namespace std;

//given an unsorted array, find kth smallest in O(n) time. 
//if k=n/2 -> the answer is the median.
//algorithm: similar to quicksort



int n;

void swap(int array[],int a,int b){
	if(a!=b){
		array[a]^=array[b];
		array[b]^=array[a];
		array[a]^=array[b];
	}
}


int partition(int array[],int lo,int hi){
	
	int pivot=array[lo];
	
	while(lo<hi){
	
		while(array[lo]<pivot)
			lo++;
			
		while(array[hi]>pivot)
			hi--;
			
		if(array[lo]==array[hi]) //duplicate
			lo++;
			
		if(lo<hi)
			swap(array,lo,hi);
		else
			break;
	}

	return hi;
}


int kth_smallest(int array[],int k,int lo,int hi){

	int pivot=partition(array,lo,hi);
	if(lo>=hi || pivot==k)
		return pivot;
	else if(k<pivot)
		kth_smallest(array,k,lo,pivot-1); //search in lo part
	else
		kth_smallest(array,k,pivot+1,hi); //search in hi part
}

int main(){

	int numbers[]={5,86,4,86,2,69,73,11,17,1,74,34,3};
	n=sizeof(numbers)/sizeof(int);
	
	int k=6; //zero based
		
	int kth_index=kth_smallest(numbers,k,0,n-1);

	cout<<"kth smallest is "<<numbers[kth_index]<<endl;


	return 0;
}























{'fraction_non_alphanumeric': 0.18241042345276873, 'fraction_numerical': 0.023615635179153095, 'mean_word_length': 3.6908396946564888, 'pattern_counts': {'":': 0, '<': 14, '<?xml version=': 0, '>': 8, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '964510', 'n_tokens_mistral': 579, 'n_tokens_neox': 509, 'n_words': 111}