linked list quick sort in c

coh·2023년 3월 14일
0

알고리즘

목록 보기
2/2
void quick_sort(t_node *left, t_node *right, int start, int end)
{
	t_deque deque;
	int		l;
	int		r;
	int		pivot;

	if (start >= end)
		return ;
	// select appropriate pivot to sort effectively.
	// In case, I select pivot as deque->top->data! 
	deque.top = left;
	deque.bottom = right;
	pivot = left->data;
	l = start + 1;
	r = end;
	// We'll use top->data, so left = left->next
	left = left->next;
	while (l <= r)
	{
		while (l <= end && pivot >= left->data)
		{
			l++;
			left = left->next;
		}
		while (start < r && pivot <= right->data)
		{
			r--;
			right = right->prev;
		}
		if (l > r)
			swap(&deque.top->data, &right->data);
		else
			swap(&left->data, &right->data);
	}
	quick_sort(deque.top, right->prev, start, r - 1);
	quick_sort(right->next, deque.bottom, r + 1, end);
}
profile
Written by coh

0개의 댓글