{"size": 2050, "ext": "js", "max_stars_repo_path": "js/algorithms/QuickSort2.js", "max_stars_repo_name": "littleark/sorting4exhibition", "max_stars_repo_stars_event_min_datetime": "2015-07-18T10:12:58.000Z", "max_stars_repo_stars_event_max_datetime": "2022-03-13T00:42:33.000Z", "max_issues_repo_path": "js/algorithms/QuickSort2.js", "max_issues_repo_name": "littleark/sorting4exhibition", "max_issues_repo_issues_event_min_datetime": "2021-07-10T11:03:39.000Z", "max_issues_repo_issues_event_max_datetime": "2021-07-10T11:03:39.000Z", "max_forks_repo_path": "js/algorithms/QuickSort2.js", "max_forks_repo_name": "littleark/sorting4exhibition", "max_forks_repo_forks_event_min_datetime": "2015-07-14T05:52:32.000Z", "max_forks_repo_forks_event_max_datetime": "2018-05-08T04:35:11.000Z"}
{"max_stars_count": 8, "max_issues_count": 1, "max_forks_count": 2, "avg_line_length": 23.2954545455, "max_line_length": 94, "alphanum_fraction": 0.567804878}
define(["../support"], function(support) {
	swap=support.swap;
	addStep=support.addStep;
	return {
		"name":"Quicksort with Partition",
		"complexity":"O(n log n)",
		"wiki":"http://en.wikipedia.org/wiki/Quicksort",
	    "code":function() {
			var steps=[];
			var comparisons=[];
			var index=[];
			var cmp=0;

			function partition(array, begin, end, pivot) {
				//console.log(array.length,begin,end,pivot)
				var piv=array[pivot];

				index.push([begin,-1,end-1,pivot]);
				comparisons.push({
            		cmp:cmp,
            		index:support.cloneArray(index)
            	});
            	index=[];

				swap(steps,array,pivot, end-1 ,comparisons[comparisons.length-1]);


				var store=begin;
				var ix;
				for(ix=begin; ix<end-1; ++ix) {
					
					index.push([store,ix,end-1,pivot]);

					if(array[ix].value<=piv.value) {

						comparisons.push({
		            		cmp:cmp,
		            		index:support.cloneArray(index)
		            	});
		            	index=[];

						swap(steps,array,store, ix,comparisons[comparisons.length-1]);
						++store;
					}
					cmp++;
				}

				index.push([store,ix,end-1,pivot]);
				comparisons.push({
            		cmp:cmp,
            		index:support.cloneArray(index)
            	});
            	index=[];
				swap(steps,array,end-1, store,comparisons[comparisons.length-1]);

				return store;
			}
			function quicksort(array, begin, end) {
				if(end-1>begin) {
					var pivot=begin+Math.floor(Math.random()*(end-begin));

					pivot=partition(array, begin, end, pivot);

					quicksort(array, begin, pivot);
					quicksort(array, pivot+1, end);
				}
			}

			return function(array) {
				steps=[];
				quicksort(array,0,array.length);
				
				steps=steps.filter(function(d){
					return d.length>0;
				});

				//console.log("STEP vs COMPLEXITY",steps.map(function(d){
					//return d[0].cmp.cmp;
				//}))
				//console.log("COMPARISONS",(comparisons))
				//console.log("COMPLEXITY",comparisons[comparisons.length-1],steps[steps.length-1][0].cmp)

				return steps;
			}

		}
	}
});